×

Forbidden subgraphs of power graphs. (English) Zbl 1467.05115

Summary: The undirected power graph (or simply power graph) of a group \(G\), denoted by \(P(G)\), is a graph whose vertices are the elements of the group \(G\), in which two vertices \(u\) and \(v\) are connected by an edge between if and only if either \(u=v^i\) or \(v=u^j\) for some \(i, j\).
A number of important graph classes, including perfect graphs, cographs, chordal graphs, split graphs, and threshold graphs, can be defined either structurally or in terms of forbidden induced subgraphs. We examine each of these five classes and attempt to determine for which groups \(G\) the power graph \(P(G)\) lies in the class under consideration. We give complete results in the case of nilpotent groups, and partial results in greater generality. In particular, the power graph is always perfect; and we determine completely the groups whose power graph is a threshold or split graph (the answer is the same for both classes). We give a number of open problems.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C17 Perfect graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

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(3):#P3.16, 2017. · Zbl 1369.05059
[2] J. Abawajy, A. Kelarev, and M. Chowdhury Power graphs: A survey.Electron. J. Graph Theory Appl., 1(2):125-147, 2013. · Zbl 1306.05090
[3] C. Berge. Perfect graphs.Six Papers on Graph Theory. Indian Statistical Institute, Calcutta, 1963, pp. 1-21.
[4] A. Brandst¨adt, V. B. Le, and J. P. Spinrad.Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999. · Zbl 0919.05001
[5] P. J. Cameron.The power graph of finite group II.Journal of Group Theory, 13(6):779-783, 2010. · Zbl 1206.20023
[6] P. J. Cameron and S. Ghosh. The power graph of a finite group.Discrete Math., 311(13):1220-1222 2011. · Zbl 1276.05059
[7] P. J. Cameron, H. Guerra, and ˇS. Jurina. The power graph of a torsion-free group. J. Algebraic Combinatorics, 49:83-98, 2019. · Zbl 1410.05085
[8] P. J. Cameron and S. H. Jafari. On the connectivity and independence number of power graphs of groups.Graphs and Combinatorics, 36:895-904, 2020. · Zbl 1481.05066
[9] I. Chakrabarty, S. Ghosh, and M. K. Sen. Undirected power graphs of semigroups. Semigroup Forum, 78:410-426, 2009. · Zbl 1207.05075
[10] S. Chattopadhyay, K. L. Patra, and B. K. Sahoo. Vertex connectivity of the power graph of a finite cyclic group.Discrete Applied Mathematics, 266:259-271, 2019. · Zbl 1464.05175
[11] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem.Annals of Mathematics, 164:51-229, 2006. · Zbl 1112.05042
[12] V. Chv´atal and P. L. Hammer. Aggregations of inequalities in integer programming. Ann. Discrete Math., 1:145-162, 1977. · Zbl 0384.90091
[13] B. Curtin, G. R. Pourgholi, and H. Yousefi-Azari. On the punctured power graph of a finite group.Australasian Journal of Combinatorics, 62(1):1-7, 2015. · Zbl 1321.05107
[14] A. Doostabadi, M. Farrokhi, and D. Ghouchan. On the connectivity of proper power graph of finite groups.Communications in Algebra, 43(10):4305-4319, 2015. · Zbl 1323.05065
[15] R. P. Dilworth. A decomposition theorem for partially ordered sets.Ann. Math., 51(1):161-166, 1950. · Zbl 0038.02003
[16] S. F¨oldes and P. L. Hammer. Split graphs having Dilworth number two.Canad. J. Math., 29(3):666-672, 1977. · Zbl 0335.05130
[17] D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs.Pacific J. Math., 15(3):835-855, 1965. · Zbl 0132.21001
[18] D. Gorenstein and J. H. Walter. On finite groups with dihedral Sylow 2-subgroups. Illinois J. Math.6(4):553-593, 1962. · Zbl 0126.05202
[19] M. Gr¨otschel, L. Lov´asz, and A. Schrijver.Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 1988. · Zbl 0634.05001
[20] Marshall Hall, Jr..The Theory of Groups. Macmillan, New York, 1959. · Zbl 0084.02202
[21] P. B. Henderson and Y. Zalcstein. A graph-theoretic characterization of the PV class of synchronizing primitives.SIAM J.Scientific Computing6(1):88-108, 1977. · Zbl 0349.68022
[22] S. H. Jafari. A description of automorphism group of power graphs of finite groups. arXiv:1902.05323, 2019.
[23] A. Kelarev and S. J. Quinn. Directed graphs and combinatorial properties of semigroups.J. Algebra, 251(1):16-26, 2002. · Zbl 1005.20043
[24] A. S. Kondrat’ev and V. D. Mazurov. Recognition of alternating groups of prime degree from the orders of their elements.Siberian Math. J., 41(2):294-302, 2000. · Zbl 0956.20007
[25] L. Lov´asz. Normal hypergraphs and the perfect graph conjecture.Discrete Mathematics, 2(3):253-267, 1972. · Zbl 0239.05111
[26] X. Ma and M. Feng. On the chromatic number of the power graph of a finite group. Indag. Math. (NS),26(4): 626-633, 2015. · Zbl 1317.05063
[27] X. Ma and H. Su. On the order supergraph of the power graph of a finite group. Ricerche mat., 2020.https://doi.org/10.1007/s11587-020-00520-w
[28] V. N. Mahadev and U. N. Peled.Threshold Graphs and Related Topics, Elsevier, 1995. · Zbl 0852.05001
[29] K. Pourghobadi and S. H. Jafari. The diameter of power graphs of symmetric groups. J. Algebra Appl., 17(12):1850234, 11pp, 2018. · Zbl 1481.20007
[30] D. P. Sumner. Dacey graphs.J. Aust. Math. Soc., 18(4):492-502, 1974. · Zbl 0314.05108
[31] N. Trotignon.Perfect graphs, in: L.W. Beineke, R.J. Wilson (Eds.), Topics in Chromatic Graph Theory, Cambridge University Press, 2015. · Zbl 1351.05094
[32] J. H. Walter. The characterization of finite groups with abelian Sylow 2-subgroups. Ann. Math., 89(3):405-514, 1969. · Zbl 0184.04605
[33] J. S. Williams. Prime graph components of finite groups.J. Algebra, 69:487-513, 1981. · Zbl 0471.20013
[34] S. Zahirovi´c.The power graph of a torsion-free group of nilpotency class 2. arXiv:1911.00555, 2019.
[35] S. Zahirovi´c. The power graph of a torsion-free group determines the directed power graph.arXiv:2006.01984, 2020
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.