Partition Dimension of Bridge Graphs Between Complete and Star Graphs
DOI:
https://doi.org/10.12962/j24775401.ijcsam.v11i2.8363Keywords:
Partition dimension, Bridge Graph, Star graph, Complete graphAbstract
This paper investigates the determination of the partition dimension for a \emph{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 \emph{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 \emph{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.
References
[1] R. P. Adirasari, H. Suprajitno, and L. Susilowati, “The dominant metric dimension of corona product graphs,” Baghdad Science Journal, vol. 18, no. 2, pp. 349–356, 2021, doi:10.21123/BSJ.2021.18.2.0349.
[2] Amrullah, D. Darmaji, and E. T. Baskoro, “The partition dimension of homogeneous firecrackers,” Far East Journal of Applied Mathematics, vol. 90, no. 1, pp. 77–98, 2015, doi:10.17654/fjamjan2015 077 098.
[3] Amrullah, “The partition dimension for a subdivision of a homogeneous firecracker,” Electronic Journal of Graph Theory and Applications, vol. 8, no. 2, pp. 445–455, 2020, doi:10.5614/ejgta.2020.8.2.20.
[4] Amrullah, B. Baidowi, S. Azmi, N. Kurniati, and T. Turmuzi, “The upper bound of metric dimension of bridge graphs,” in Advances in Social Science, Education and Humanities Research, vol. 465, pp. 4–8, 2020, doi:10.2991/assehr.k.200827.002. (Proceedings ACCESS 2019.)
[5] A. Amrullah, A. Syahrul, M. Turmuzi, Baidowi, and K. Nani, “The bridge graphs partition dimension,” Journal of Physics: Conference Series, vol. 1779, no. 1, p. 012086, 2021, doi:10.1088/1742-6596/1779/1/012086.
[6] K. I. B. K. P. Arimbawa and E. T. Baskoro, “Partition dimension of some classes of trees,” Procedia Computer Science, vol. 74, pp. 67–72, 2015, doi:10.1016/j.procs.2015.12.077.
[7] M. I. Batiha, M. Amin, B. Mohamed, and H. I. Jebril, “Connected metric dimension of the class of ladder graphs,” Mathematical Models in Engineering, vol. 10, no. 2, pp. 65–74, 2024, doi:10.21595/mme.2024.23934.
[8] S. A. U. H. Bokhary, A. Kharal, F. M. A. Samman, M. E. E. Dalam, and A. Gargouri, “Efficient graph algorithms in securing communication networks,” Symmetry, vol. 16, no. 10, 2024, doi:10.3390/sym16101269.
[9] H. Casta˜neda-L´opez, P. C. Palomino, A. B. Ramos-Tort, C. Rubio-Montiel, and C. Silva-Ruiz, “The 6-girth-thickness of the complete graph,” AKCE International Journal of Graphs and Combinatorics, vol. 17, no. 3, pp. 856–861, 2020, doi:10.1016/j.akcej.2019.05.004.
[10] Chartrand, G., Salehi, E., Zhang, P. (2000). The partition dimension of a graph. Aequationes mathematicae, 59(1), 45-54.
[11] S. Ezhilarasi and M. Kavitha, “A study on labelling for star graphs,” Malaya Journal of Matematik, vol. S, no. 1, pp. 377–379, 2021.
[12] H. Fernau and J. A. Rodriguez-Velazquez, “On the (adjacency) metric dimension of corona and strong product graphs and their local variants: Combinatorial and computational results,” Discrete Applied Mathematics, vol. 236, pp. 183–202, 2018, doi:10.1016/j.dam.2017.11.019.
[13] K. Q. Fredlina and E. T. Baskoro, “The partition dimension of some families of trees,” Procedia Computer Science, vol. 74, pp. 60–66, 2015, doi:10.1016/j.procs.2015.12.076.
[14] I. Gonz´alez Yero, M. Jakovac, D. Kuziak, and A. Taranenko, “The partition dimension of strong product graphs and Cartesian product graphs,” Discrete Mathematics, vol. 331, pp. 43–52, 2014, doi:10.1016/j.disc.2014.04.026.
[15] Haryeni, D. O., Baskoro, E. T., Saputro, S. W. Family of graphs with partition dimension three. Indonesian Journal of Combinatorics, 8(2), 64-75, 2024.
[16] Z. Hussain, S. M. Kang, M. Rafique, M. Munir, U. Ali, A. Zahid, and M. S. Saleem, “Bounds for partition dimension of M-wheels,” Open Physics, vol. 17, no. 1, pp. 340–344, 2019, doi:10.1515/phys-2019-0037.
[17] A. N. A. Koam, A. Ahmad, M. S. Alatawi, A. Khalil, and M. Azeem, “On the constant partition dimension of some generalized families of Toeplitz graph,” Journal of Mathematics, 2024, doi:10.1155/2024/4721104.
[18] C. M. Mohan, S. Santhakumar, M. Arockiaraj, and J. B. Liu, “Partition dimension of certain classes of series parallel graphs,” Theoretical Computer Science, vol. 778, pp. 47–60, 2019, doi:10.1016/j.tcs.2019.01.026.
[19] S. Prabhu, T. J. Janany, and S. Klavzar, “Metric dimensions of generalized Sierpi´nski graphs over squares,” Applied Mathematics and Computation, vol. 505, p. 129528, 2025, doi:10.1016/j.amc.2025.129528.
[20] H. Raza, J. B. Liu, M. Azeem, and M. F. Nadeem, “Partition dimension of generalized Petersen graph,” Complexity, 2021, doi:10.1155/2021/5592476.
[21] J. Santoso and D. Darmaji, “The partition dimension of cycle books graph,” Journal of Physics: Conference Series, vol. 974, no. 1, p. 012070, 2018, doi:10.1088/1742-6596/974/1/012070.
[22] Stampfli, M. Bridged graphs, circuits and Fibonacci numbers. Applied Mathematics and Computation, 302, 68-79, 2017.
[23] S. Zahidah, L. Susilowati, and E. Lusvianto, “The dominant metric dimension of the edge corona product graph,” Baghdad Science Journal, vol. 18, no. 2, 2021, doi:10.21123/bsj.2021.18.2.0349.
