Let $ G $ be a finite group. The reduced power graph of $ G $ is the undirected graph whose vertex set consists of all elements of $ G $, and two distinct vertices $ x $ and $ y $ are adjacent if either $ \langle x\rangle \subset \langle y\rangle $ or $ \langle y\rangle \subset \langle x\rangle $. In this paper, we show that the reduced power graph of $ G $ is perfect and characterize all finite groups whose reduced power graphs are split graphs, cographs, chordal graphs, and threshold graphs. We also give complete classifications in the case of abelian groups, dihedral groups, and generalized quaternion groups.
Citation: Huani Li, Ruiqin Fu, Xuanlong Ma. Forbidden subgraphs in reduced power graphs of finite groups[J]. AIMS Mathematics, 2021, 6(5): 5410-5420. doi: 10.3934/math.2021319
Let $ G $ be a finite group. The reduced power graph of $ G $ is the undirected graph whose vertex set consists of all elements of $ G $, and two distinct vertices $ x $ and $ y $ are adjacent if either $ \langle x\rangle \subset \langle y\rangle $ or $ \langle y\rangle \subset \langle x\rangle $. In this paper, we show that the reduced power graph of $ G $ is perfect and characterize all finite groups whose reduced power graphs are split graphs, cographs, chordal graphs, and threshold graphs. We also give complete classifications in the case of abelian groups, dihedral groups, and generalized quaternion groups.
| [1] | G. Aalipour, S. Akbari, P. J. Cameron, R. Nikandish, F. Shaveisi, On the structure of the power graph and the enhanced power graph of a group, Electron. J. Combin., 24 (2017), 3–16. |
| [2] | J. Abawajy, A. Kelarev, M. Chowdhury, Power graphs: A survey, Electron. J. Graph Theory Appl., 1 (2013), 125–147. |
| [3] |
T. Anitha, R. Rajkumar, On the power graph and the reduced power graph of a finite group, Commun. Algebra, 47 (2019), 3329–3339. doi: 10.1080/00927872.2018.1555842
|
| [4] |
T. Anitha, R. Rajkumar, Characterization of groups with planar, toroidal or projective planar (proper) reduced power graphs, J. Algebra Appl., 19 (2020), 2050099. doi: 10.1142/S0219498820500991
|
| [5] | B. Bollobás, Mordern graph theory, New York: Springer, 1998. |
| [6] |
D. Bubboloni, M. A. Iranmanesh, S. M. Shaker, Quotient graphs for power graphs, Rend. Semin. Mat. Univ. Padova, 138 (2017), 61–89. doi: 10.4171/RSMUP/138-3
|
| [7] | P. J. Cameron, The power graph of a finite group, II, J. Group Theory, 13 (2010), 779–783. |
| [8] |
P. J. Cameron, S. Ghosh, The power graph of a finite group, Discrete Math., 311 (2011), 1220–1222. doi: 10.1016/j.disc.2010.02.011
|
| [9] | P. J. Cameron, P. Manna, R. Mehatari, Forbidden subgraphs of power graphs, Preprint, 2020. Available from: arXiv: 2010.05198v2. |
| [10] |
I. Chakrabarty, S. Ghosh, M. K. Sen, Undirected power graphs of semigroups, Semigroup Forum, 78 (2009), 410–426. doi: 10.1007/s00233-008-9132-y
|
| [11] |
M. Deaconescu, Classification of finite groups with all elements of prime order, Proc. Am. Math. Soc., 106 (1989), 625–629. doi: 10.1090/S0002-9939-1989-0969518-2
|
| [12] |
A. Doostabadi, A. Erfanian, D. G. M. Farrokhi, On power graphs of finite groups with forbidden induced subgraphs, Indagat. Math. (NS), 25 (2014), 525–533. doi: 10.1016/j.indag.2014.01.003
|
| [13] |
M. Feng, X. Ma, K. Wang, The structure and metric dimension of the power graph of a finite group, Eur. J. Combin., 43 (2015), 82–97. doi: 10.1016/j.ejc.2014.08.019
|
| [14] | S. Foldes, P. L. Hammer, Split graphs, In: Proceedings of the $8$th South-Eastern Conference on Combinatorics, Graph Theory and Computing, (1977), 311–315. |
| [15] | D. Gorenstein, Finite groups, New York: Chelsea Publishing Co., 1980. |
| [16] |
G. Higman, Finite groups in which every element has prime power order, J. London Math. Soc., s1-32 (1957), 335–342. doi: 10.1112/jlms/s1-32.3.335
|
| [17] | D. L. Johnson, Topics in the theory of group presentations, London Math. Soc. Lecture Note Ser., Cambridge University Press, 1980. |
| [18] | A. V. Kelarev, Ring constructions and applications, World Scientific, 2002. |
| [19] | A. V. Kelarev, Graph algebras and automata, New York: Marcel Dekker, 2003. |
| [20] | A. V. Kelarev, Labelled Cayley graphs and minimal automata, Australas. J. Combin., 30 (2004), 95–101. |
| [21] | A. V. Kelarev, S. J. Quinn, A combinatorial property and power graphs of groups, Contrib. General Algebra, 12 (2000), 229–235. |
| [22] |
A. V. Kelarev, J. Ryan, J. Yearwood, Cayley graphs as classifiers for data mining: The influence of asymmetries, Discrete Math., 309 (2009), 5360–5369. doi: 10.1016/j.disc.2008.11.030
|
| [23] |
X. Ma, Perfect codes in proper reduced power graphs of finite groups, Commun. Algebra, 48 (2020), 3881–3890. doi: 10.1080/00927872.2020.1749845
|
| [24] |
X. Ma, G. L. Walls, K. Wang, Power graphs of (non) orientable genus two, Commun. Algebra, 47 (2019), 276–288. doi: 10.1080/00927872.2018.1476522
|
| [25] |
A. R. Moghaddamfar, S. Rahbariyan, W. J. Shi, Certain properties of the power graph associated with a finite group, J. Algebra Appl., 13 (2014), 1450040. doi: 10.1142/S0219498814500406
|
| [26] |
R. Rajkumar, T. Anitha, Reduced power graph of a group, Electron. Notes Discrete Math., 63 (2017), 69–76. doi: 10.1016/j.endm.2017.10.063
|
| [27] | R. Rajkumar, T. Anitha, Some results on the reduced power graph of a group, Southeast Asian Bull. Math., 2018. Available from: arXiv: 1804.00728v2. |
| [28] | D. B. West, Introduction to graph theory, 2 Eds., Englewood Cliffs, NJ: Prentice Hall, 2001. |
Huani Li, Ruiqin Fu, Xuanlong Ma. Forbidden subgraphs in reduced power graphs of finite groups[J]. AIMS Mathematics, 2021, 6(5): 5410-5420. doi: 10.3934/math.2021319
DownLoad: