Research ArticleNo Access

The metric dimension of the enhanced power graph of a finite group

Xuanlong Ma

School of Science, Xi’an Shiyou University, Xi’an 710065, P. R. China

E-mail Address: xuanlma@mail.bnu.edu.cn

Search for more papers by this author

and

Yanhong She

School of Science, Xi’an Shiyou University, Xi’an 710065, P. R. China

E-mail Address: yanhongshe@xsyu.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0219498820500206Cited by:15 (Source: Crossref)

Abstract

The enhanced power graph of a finite group $G$ is the graph whose vertex set is $G$ , and two distinct vertices are adjacent if they generate a cyclic subgroup of $G$ . In this paper, we establish an explicit formula for the metric dimension of an enhanced power graph. As an application, we compute the metric dimension of the enhanced power graph of an elementary abelian $p$ -group, a dihedral group and a generalized quaternion group.

Communicated by T. H. Ha

Keywords:

AMSC: 05C25, 05C69

References

1. G. Aalipour, S. Akbari, P. J. Cameron, R. Nikandish and F. Shaveisi , On the structure of the power graph and the enhanced power graph of a group, Electron. J. Combin. 24 (2017) #P3.16. Crossref, Web of Science, Google Scholar
2. J. Abawajy, A. Kelarev and M. Chowdhury , Power graphs: A survey, Electron. J. Graph Theory Appl. 1 (2013) 125–147. Crossref, Google Scholar
3. J. Abawajy, A. V. Kelarev, M. Miller and J. Ryan , Rees semigroups of digraphs for classification of data, Semigroup Forum 92 (2016) 121–134. Crossref, Web of Science, Google Scholar
4. R. F. Bailey and P. J. Cameron , Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc. 43 (2011) 209–242. Crossref, Web of Science, Google Scholar
5. S. J. Baishya , A note on finite C-tidy groups, Int. J. Group Theory 2 (2013) 9–17. Google Scholar
6. S. Bera and A. K. Bhuniya , On enhanced power graphs of finite groups, J. Algebra Appl. 17 (2018) 1850146. Link, Web of Science, Google Scholar
7. R. Brauer and K. A. Fowler , On groups of even order, Ann. Math. 62 (1955) 567–583. Crossref, Web of Science, Google Scholar
8. D. Bubboloni, M. A. Iranmanesh and S. M. Shaker , On some graphs associated with the finite alternating groups, Commun. Algebra 45 (2017) 5355–5373. Crossref, Web of Science, Google Scholar
9. D. Bubboloni, M. A. Iranmanesh and S. M. Shaker , Quotient graphs for power graphs, Rend. Semin. Mat. Univ. Padova 138 (2017) 61–89. Crossref, Web of Science, Google Scholar
10. J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara and D. R. Wood , On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423–441. Crossref, Web of Science, Google Scholar
11. P. J. Cameron , The power graph of a finite group, II, J. Group Theory 13 (2010) 779–783. Crossref, Web of Science, Google Scholar
12. P. J. Cameron and S. Ghosh , The power graph of a finite group, Discrete Math. 311 (2011) 1220–1222. Crossref, Web of Science, Google Scholar
13. I. Chakrabarty, S. Ghosh and M. K. Sen , Undirected power graphs of semigroups, Semigroup Forum 78 (2009) 410–426. Crossref, Web of Science, Google Scholar
14. 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. Crossref, Web of Science, Google Scholar
15. L. A. Dupont, D. G. Mendoza and M. Rodríguez, The rainbow connection number of enhanced power graph, arXiv:1708.07598 [math.CO]. Google Scholar
16. M. Feng, X. Ma and K. Wang , The structure and metric dimension of the power graph of a finite group, Eur. J. Combin. 43 (2015) 82–97. Crossref, Web of Science, Google Scholar
17. M. Feng, X. Ma and K. Wang , The full automorphism group of the power (di)graph of a finite group, Eur. J. Combin. 52 (2016) 197–206. Crossref, Web of Science, Google Scholar
18. M. R. Garey and D. S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). Google Scholar
19. D. Gorenstein , Finite Groups (Chelsea Publishing Co., New York, 1980). Google Scholar
20. F. Harary and R. A. Melter , On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195. Google Scholar
21. C. Hernando, M. Mora, I. M. Pelayo, C. Seara and D. R. Wood , Extremal graph theory for metric dimension and diameter, Electron. J. Combin. 17 (2010) #R30. Crossref, Web of Science, Google Scholar
22. A. V. Kelarev , Graph Algebras and Automata (Marcel Dekker, New York, 2003). Crossref, Google Scholar
23. A. V. Kelarev , Labelled Cayley graphs and minimal automata, Australas. J. Combin. 30 (2004) 95–101. Google Scholar
24. A. V. Kelarev and S. J. Quinn , A combinatorial property and power graphs of groups, Contrib. Gen. Algebra 12 (2000) 229–235. Google Scholar
25. A. V. Kelarev and S. J. Quinn , Directed graphs and combinatorial properties of semigroups, J. Algebra 251 (2002) 16–26. Crossref, Web of Science, Google Scholar
26. A. V. Kelarev and S. J. Quinn , A combinatorial property and power graphs of semigroups, Comment. Math. Uni. Carolinae 45 (2004) 1–7. Google Scholar
27. A. V. Kelarev, S. J. Quinn and R. Smolikova , Power graphs and semigroups of matrices, Bull. Austral. Math. Soc. 63 (2001) 341–344. Crossref, Web of Science, Google Scholar
28. A. V. Kelarev, J. Ryan and J. Yearwood , Cayley graphs as classifiers for data mining: The inuence of asymmetries, Discret. Math. 309 (2009) 5360–5369. Crossref, Web of Science, Google Scholar
29. S. Khuller, B. Raghavachari and A. Rosenfeld , Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. Crossref, Web of Science, Google Scholar
30. X. Ma and M. Feng , On the chromatic number of the power graph of a finite group, Indag. Math. (NS) 26 (2015) 626–633. Crossref, Web of Science, Google Scholar
31. X. Ma, M. Feng and K. Wang , The rainbow connection number of the power graph of a finite group, Graphs Combin. 32 (2016) 1495–1504. Crossref, Web of Science, Google Scholar
32. X. Ma, M. Feng and K. Wang , The power index of a graph, Graphs Combin. 33 (2017) 1381–1391. Crossref, Web of Science, Google Scholar
33. X. Ma, M. Feng and K. Wang , The strong metric dimension of the power graph of a finite group, Discrete Appl. Math. 239 (2018) 159–164. Crossref, Web of Science, Google Scholar
34. D. L. Johnson , Topics in the Theory of Group Presentations, London Mathematical Society Lecture Note Series, Vol. 42 (Cambridge University Press, 1980). Crossref, Google Scholar
35. K. O’Bryant, D. Patrick, L. Smithline and E. Wepsic, Some facts about cycles and tidy groups, Technical Report, MS–TR 92–04, Rose–Hulman Institute of Technology, Terre Haute, Ind, USA (1992). Google Scholar
36. D. Patrick and E. Wepsic, Cyclicizers, centralizers and normalizers, Technical Report, MS–TR 91–05, Rose–Hulman Institute of Technology, Terre Haute, Ind, USA (1991). Google Scholar
37. P. J. Slater , Leaves of trees, Congr. Numer. 14 (1975) 549–559. Google Scholar