In this study, we explore the main supergraph $ \mathcal{S}(G) $ of a finite group $ G $, defined as an undirected, simple graph with a vertex set $ G $ in which two distinct vertices, $ a $ and $ b $, are adjacent in $ \mathcal{S}(G) $ if the order of one is a divisor of the order of the other. This is denoted as either $ o(a)\mid o(b) $ or $ o(b)\mid o(a) $, where $ o(\cdot) $ is the order of an element. We classify finite groups for which the main supergraph is either a split graph or a threshold graph. Additionally, we characterize finite groups whose main supergraph is a cograph. Our classification extends to finite groups $ G $ with $ \mathcal{S}(G) $, a cograph that includes when $ G $ is a direct product of two non-trivial groups, as well as when $ G $ is either a dihedral group, a generalized quaternion group, a symmetric group, an alternating group, or a sporadic simple group.
Citation: Xiaoyan Xu, Xiaohua Xu, Jin Chen, Shixun Lin. On forbidden subgraphs of main supergraphs of groups[J]. Electronic Research Archive, 2024, 32(8): 4845-4857. doi: 10.3934/era.2024222
In this study, we explore the main supergraph $ \mathcal{S}(G) $ of a finite group $ G $, defined as an undirected, simple graph with a vertex set $ G $ in which two distinct vertices, $ a $ and $ b $, are adjacent in $ \mathcal{S}(G) $ if the order of one is a divisor of the order of the other. This is denoted as either $ o(a)\mid o(b) $ or $ o(b)\mid o(a) $, where $ o(\cdot) $ is the order of an element. We classify finite groups for which the main supergraph is either a split graph or a threshold graph. Additionally, we characterize finite groups whose main supergraph is a cograph. Our classification extends to finite groups $ G $ with $ \mathcal{S}(G) $, a cograph that includes when $ G $ is a direct product of two non-trivial groups, as well as when $ G $ is either a dihedral group, a generalized quaternion group, a symmetric group, an alternating group, or a sporadic simple group.
| [1] | A. Kelarev, Ring Constructions and Applications, World Scientific Publishing, Singapore, 2002. https://doi.org/10.1142/4807 |
| [2] |
A. Kelarev, J. Ryan, J. Yearwood, Cayley graphs as classifiers for data mining: The influence of asymmetries, Discrete Math., 309 (2009), 5360–5369. https://doi.org/10.1016/j.disc.2008.11.030 doi: 10.1016/j.disc.2008.11.030
|
| [3] | A. Kelarev, S. Quinn, A combinatorial property and power graphs of groups, Contrib. Gen. Algebra, 12 (2000), 229–235. |
| [4] |
I. Chakrabarty, S. Ghosh, M. Sen, Undirected power graphs of semigroups, Semigroup Forum, 78 (2009), 410–426. https://doi.org/10.1007/s00233-008-9132-y doi: 10.1007/s00233-008-9132-y
|
| [5] |
G. Pourgholi, H. Yousefi-Azari, A. Ashrafi, The undirected power graph of a finite group, Bull. Malays. Math. Sci. Soc., 38 (2015), 1517–1525. https://doi.org/10.1007/s40840-015-0114-4 doi: 10.1007/s40840-015-0114-4
|
| [6] | J. Abawajy, A. Kelarev, M. Chowdhury, Power graphs: A survey, Electron. J. Graph Theory Appl., 1 (2013), 125–147. http://doi.org/10.5614/ejgta.2013.1.2.6 |
| [7] |
A. Kumar, L. Selvaganesh, P. Cameron, T. Chelvam, Recent developments on the power graph of finite groups - a survey, AKCE Int. J. Graphs Comb., 18 (2021), 65–94. https://doi.org/10.1080/09728600.2021.1953359 doi: 10.1080/09728600.2021.1953359
|
| [8] |
G. Cutolo, On a construction by Giudici and Parker on commuting graphs of groups, J. Comb. Theory Ser. A, 192 (2022), 105666. https://doi.org/10.1016/j.jcta.2022.105666 doi: 10.1016/j.jcta.2022.105666
|
| [9] |
A. Abdollahi, S. Akbari, H. Maimani, Non-commuting graph of a group, J. Algebra, 298 (2006), 468–492. https://doi.org/10.1016/j.jalgebra.2006.02.015 doi: 10.1016/j.jalgebra.2006.02.015
|
| [10] |
J. Dutta, R. Nath, Spectrum of commuting graphs of some classes of finite groups, Matematika, 33 (2017), 87–95. https://doi.org/10.11113/matematika.v33.n1.812 doi: 10.11113/matematika.v33.n1.812
|
| [11] |
P. Dutta, J. Dutta, R. Nath, On Laplacian spectrum of non-commuting graphs of finite groups, Indian J. Pure Appl. Math., 49 (2018), 205–216. https://doi.org/10.1007/s13226-018-0263-x doi: 10.1007/s13226-018-0263-x
|
| [12] |
A. Hamzeh, A. Ashrafi, Automorphism groups of supergraphs of the power graph of a finite group, Eur. J. Comb., 60 (2017), 82–88. https://doi.org/10.1016/j.ejc.2016.09.005 doi: 10.1016/j.ejc.2016.09.005
|
| [13] |
A. Hamzeh, A. Ashrafi, The order supergraph of the power graph of a finite group, Turk. J. Math., 42 (2018), 1978–1989. https://doi.org/10.3906/mat-1711-78 doi: 10.3906/mat-1711-78
|
| [14] |
X. Ma, H. Su, On the order supergraph of the power graph of a finite group, Ric. Mat., 71 (2022), 381–390. https://doi.org/10.1007/s11587-020-00520-w doi: 10.1007/s11587-020-00520-w
|
| [15] |
A. Hamzeh, A. Ashrafi, Some remarks on the order supergraph of the power graph of a finite group, Int. Electron. J. Algebra, 26 (2019), 1–12. https://doi.org/10.24330/ieja.586838 doi: 10.24330/ieja.586838
|
| [16] |
A. Hamzeh, A. Ashrafi, Spectrum and $L$-spectrum of the power graph and its main supergraph for certain finite groups, Filomat, 31 (2017), 5323–5334. https://doi.org/10.2298/FIL1716323H doi: 10.2298/FIL1716323H
|
| [17] |
A. Asboei, S. Salehi, Some results on the main supergraph of finite groups, Algebra Discrete Math., 30 (2020), 172–178. http://doi.org/10.12958/adm584 doi: 10.12958/adm584
|
| [18] | A. Asboei, S. Salehi, The main supergraph of finite groups, N. Y. J. Math., 28 (2022), 1057–1063. Available from: https://nyjm.albany.edu/j/2022/28-43.html. |
| [19] |
S. Foldes, P. Hammer, Split graphs having Dilworth number two, Canad. J. Math., 29 (1977), 666–672. https://doi.org/10.4153/CJM-1977-069-1 doi: 10.4153/CJM-1977-069-1
|
| [20] |
P. Henderson, Y. Zalcstein, A graph-theoretic characterization of the PVchunk class of synchronizing primitives, SIAM J. Comput., 6 (1977), 88–108. https://doi.org/10.1137/0206008 doi: 10.1137/0206008
|
| [21] |
P. Cameron, Graphs defined on groups, Int. J. Group Theory, 11 (2022), 53–107. https://doi.org/10.22108/IJGT.2021.127679.1681 doi: 10.22108/IJGT.2021.127679.1681
|
| [22] |
G. Arunkumar, P. Cameron, R. Nath, L. Selvaganesh, Super graphs on groups, Ⅰ, Graphs Comb., 38 (2022), 100. https://doi.org/10.1007/s00373-022-02496-w doi: 10.1007/s00373-022-02496-w
|
| [23] |
P. Manna, P. Cameron, R. Mehatari, Forbidden subgraphs of power graphs, Electron. J. Comb., 28 (2021), P3.4. https://doi.org/10.37236/9961 doi: 10.37236/9961
|
| [24] |
A. Delgado, Y. Wu, On locally finite groups in which every element has prime power order, Illinois J. Math., 46 (2002), 885–891. https://doi.org/10.1215/ijm/1258130990 doi: 10.1215/ijm/1258130990
|
| [25] | D. Johnson, Topics in the Theory of Group Presentations, Cambridge University Press, Cambridge, 1980. https://doi.org/10.1017/CBO9780511629303 |
| [26] |
P. Cameron, P. Manna, R. Mehatari, On finite groups whose power graph is a cograph, J. Algebra, 591 (2022), 59–74. https://doi.org/10.1016/j.jalgebra.2021.09.034 doi: 10.1016/j.jalgebra.2021.09.034
|
| [27] | J. Conway, R. Curtis, S. Norton, R. Parker, R. Wilson, $\mathbb{ATLAS}$ of Finite Groups, Oxford University Press, Oxford, 1985. |
| [28] |
H. Besche, B. Eick, E. O'Brien, A millennium project: Constructing small groups, Int. J. Algebra Comput., 12 (2002), 623–644. https://doi.org/10.1142/S0218196702001115 doi: 10.1142/S0218196702001115
|
| [29] | GAP, GAP - Groups, Algorithms, Programming - a System for Computational Discrete Algebra, 2024. Available from: http://gap-system.org. |
Xiaoyan Xu, Xiaohua Xu, Jin Chen, Shixun Lin. On forbidden subgraphs of main supergraphs of groups[J]. Electronic Research Archive, 2024, 32(8): 4845-4857. doi: 10.3934/era.2024222
DownLoad: