Partition Dimension of Bridge Graphs Between Complete and Star Graphs - Amrullah Amrullah; Laila Hayati; Junaidi Junaidi ((IJCSAM) International Journal of Computing Science and Applied Mathematics, 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 $n\ge 2$. 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 $m\le n$, and$pd(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.