The metric dimension of comb product graphs. (English) Zbl 1474.05118

Summary: A set of vertices \(W\) resolves a graph \(G\) if every vertex is uniquely determined by its coordinate of distance to the vertices in \(W\). The minimum cardinality of a resolving set of \(G\) is called the metric dimension of \(G\). In this paper, we consider a graph which is obtained by the comb product between two connected graphs. Let \(o\) be a vertex of \(H\). The comb product between \(G\) and \(H\), denoted by \(G\rhd_o H\), is a graph obtained by taking one copy of \(G\) and \(|V(G)|\) copies of \(H\) and identifying the \(i\)-th copy of \(H\) at the vertex \(o\) to the \(i\)-th vertex of \(G\). We give an exact value of the metric dimension of \(G\rhd_o H\) where \(H\) is not a path or \(H\) is a path where the vertex \(o\) is not a leaf. We also give the sharp general bounds of \(\beta(G\rhd_o P_n)\) for \(n\geq 2\) where the vertex \(o\) is a leaf of \(P_n\).


05C12 Distance in graphs
05C76 Graph operations (line graphs, products, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: Link


[1] M. Azari, A. Iranmanesh,Chemical graphs constructed from rooted product and their Zagreb indices, MATCH Commun. Math. Comput. Chem.70(2013), 901-919. · Zbl 1299.05043
[2] M. Baˇca, E. T. Baskoro, A. N. M. Salman, S. W. Saputro, D. Suprijanto,The metric dimension of regular bipartite graphs, Bull. Math. Soc. Sci. Math. Roumanie,54 (102)(1) (2011), 15-28 · Zbl 1224.05131
[3] P. S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang,Onk-dimensional graphs and their bases, Period. Math. Hungar.46(1) (2003), 9-15. · Zbl 1026.05033
[4] J. Caceres, C. Hernando, M. Mora, M. L. Puertas, I. M. Pelayo, C. Seara, D. R. Wood,On the metric dimension of some families of graphs, Electronic Notes in Discrete Math.22(2005), 129-133. · Zbl 1182.05050
[5] G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann,Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math.105(2000), 99-113. · Zbl 0958.05042
[6] M. Fehr, S. Gosselin, O. R. Oellermann,The metric dimension of Cayley digraphs, Discrete Math.306(2006), 31-41. · Zbl 1085.05034
[7] M. R. Garey, D. S. Johnson,Computers and Intractibility: A Guide to the Theory of NP Completeness, W. H. Freeman and Company, 1979. · Zbl 0411.68039
[8] F. Harary, R. A. Melter,On the metric dimension of a graph, Ars Combin.2(1976), 191-195. · Zbl 0349.05118
[9] M. Imran, A. Q. Baig, S. A. U. H. Bokhary, I. Javaid,On the metric dimension of circulant graphs, Appl. Math. Letters,25(2012), 320-325. · Zbl 1243.05072
[10] H. Iswadi, E. T. Baskoro, R. Simanjuntak,On the metric dimension of corona product of graphs, Far East J. Math. Sci.52(2) (2011), 155-170. · Zbl 1252.05051
[11] G. Kabatianski, V. S. Lebedev, J. Thorpe,The mastermind game and the rigidity of Hamming spaces, Proc. IEEE International Symposium on Information Theory (ISIT ’00) IEEE, (2000), 375.
[12] P. Manuel, B. Rajan, I. Rajasingh,On minimum metric dimension of honeycomb networks, J. Discrete Algorithms,6(2008) 20-27. · Zbl 1159.05308
[13] R. A. Melter, I. Tomescu,Metric bases in digital geometry, Comput. Vision, Grapichs, Image Process,25(1984), 113-121. · Zbl 0591.51023
[14] C. Poisson, P. Zhang,The metric dimension of unicyclic graphs, J. Combin. Math. Combin. Comput.40(2002), 17-32. · Zbl 0990.05040
[15] J. A. Rodr´ıguez-Vel´azquez, D. Kuziak, I. G. Yero, J. M. Sigarreta,The metric dimension of strong product graphs, arXiv:1305. 0363v1, (2013).
[16] S. W. Saputro, E. T. Baskoro, A. N. M. Salman, D. Suprijanto,The metric dimension of a completen-partite graph and its Cartesian product with a path, J. Combin. Math. Combin. Comput.71(2009), 283-293. · Zbl 1197.05037
[17] S. W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. T. Baskoro, A. N. M. Salman, M. Baˇca,The metric dimension of the lexicographic product of graphs,Discrete Math. 313(2013), 1045-1051. · Zbl 1263.05085
[18] A. Seb˝o, E. Tannier,On metric generators of graphs, Math. Oper. Res.29(2) (2004), 383-393. · Zbl 1082.05032
[19] B. Shanmukha, B. Sooryanarayana, K. S. Harinath,Metric dimension of wheels, Far East J. Appl. Math,8(3) (2002), 217-229. · Zbl 1032.05044
[20] P. J. Slater,Leaves of trees, Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Vol14of Congr. Numer. (1975), 549-559.
[21] I. G. Yero, D. Kuziak, J. A. Rodriguez-Vel´azquez,On the metric dimension of corona product graphs, Comput. Math. Appl.61(2011), 2793-2798 · Zbl 1221.05252
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.