Partition Dimension of Bridge Graphs Between Complete and Star Graphs - Amrullah Amrullah; Laila Hayati; Junaidi Junaidi (LPPM Institut Teknologi Sepuluh Nopember, 2025)
This paper investigates the determination of the partition dimension for a bridge graph formed by connecting a clique K_n and a star K_1,m through a single edge. Although the partition dimension has been extensively studied for various families and graph operations, the mixed dense–sparse case on B(K_n,K_1,m) remains unsettled, since the result is sensitive to the position of the bridge edge and the balance between the size parameters n and m.We combine distance symmetry arguments, leaf-based constraints at the star center, and explicit constructions of distinguishing partitions to obtain tight values of the partition dimension. The study begins with the basic cases K_1 and K_2, and then proceeds to the general case with parameters n2. The main result shows that for the central bridge (e=v_1x), it holds that pd(B)=n-1 if m<n, pd(B)=n if m=n, and pd(B)=m if m>n; for the leaf bridge (e=v_1u_1), it holds that pd(B)=n when mn, andpd(B)=m-1 when m>n. These results demonstrate that the location of the bridge edge, together with the size parameters m and n of the components, can sharpen the partition dimension value of the graph prior to the bridging operation.