Family of Graphs with Partition Dimension Three

Debi Oktia Haryeni, Edy Tri Baskoro, Suhadi Wido Saputro

Abstract


The characterization of all connected graphs of order n ≥3 with partition dimension 2, n−1 or n has been completely done. Additionally, all connected graphs of order n≥9 with partition dimension n−2 and graphs of order n≥11 with partition dimension n−3 have been characterized as well. However, the characterization of all connected graphs with partition dimension 3 is an open problem. In this paper, we construct many families of disconnected as well as connected graphs with partition dimension 3 by generalizing the concept of the partition dimension so that it can be applied to disconnected graphs.

Keywords


connected, disconnected, graph, partition dimension

Full Text:

PDF

DOI: http://dx.doi.org/10.19184/ijc.2024.8.2.1

References

E. T. Baskoro and D. O. Haryeni, All graphs of order n ≥ 11 and diameter 2 with partition dimension n−3, Heliyon, 6, (2020) e03694.

J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas and C. Seara, On the metric dimension of some families of graphs, Electron. Notes Discrete Math., 22 (2005), 129--133.

J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara and D. Wood, On the metric dimension of cartesian products of graphs, SIAM Journal Discrete Math., 21 (2007), 423--441.

G. Chartrand, E. Salehi and P. Zhang, On the partition dimension of a graph, Congr. Numer., 131 (1998), 55--66.

G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequationes Math, 59 (2000), 45--54.

G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000), 99-113.

F. Harary and R. A. Melter, On the metric dimension of graph, Ars. Combin., 2 (1976), 191--195.

D. O. Haryeni and E. T. Baskoro, Graph with partition dimension 3 and locating-chromatic number 4, Proceedings of the 1st International MIPAnet Conference on Science and Mathematics - IMC-SciMath, 1 (2019), 14--19.

D. O. Haryeni, E. T. Baskoro and S. W. Saputro, Partition dimension of some classes of homogeneous disconnected graphs, Procedia Comput. Sci., 74 (2015), 73--78.

D. O. Haryeni, E. T. Baskoro and S. W. Saputro, On the partition dimension of disconnected graphs, J. Math. Fund. Sci., 49 (2017), 18--32.

D. O. Haryeni, E. T. Baskoro, S. W. Saputro, M. Bača and A. Semaničová-Feňovčíková, On the partition dimension of two-component graphs, Proc. Indian Acad. Sci. (Math. Sci.), 127 (2017), 755--767.

D. O. Haryeni, M. Ridwan, and E.T. Baskoro, All graphs of order $n$ with partition dimension $n-3$, IAENG Int. J. Appl. Math., 53 (1) (2023), 152--161.

M. A. Johnson, Structure activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist, 3 (1993), 203-236.

S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217--229.

C. Poisson and P. Zhang, The metric dimension of unicyclic graphs, J. Combin. Math. Combin. Comput., 40 (2002), 17--32.

J. A. Rodríguez-Velázquez, I. G. Yero and D. Kuziak, The partition dimension of corona product graphs, Ars. Combin., 127 (2016), 387--399.

P. J. Slater, Leaves of trees, Congr. Numer., 14(1975), 549-559.

I. Tomescu, Discrepancies between metric dimension and partition dimension of a connected graph, Discrete Math., 308, (2008) 5026--5031.

I. G. Yero, M. Jakovac, D. Kuziak and A. Taranenko, The partition dimension of strong product graphs and cartesian product graphs, Discrete Math., 331 (2014), 43--52.

I. G. Yero, D. Kuziak and J. A. Rodríguez-Velázquez, A note on the partition dimension of cartesian product graphs, Appl. Math. Comput., 217 (2010), 3571--3574.


Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats