Graphs defined on groups

Document Type : Research Paper

Author

School of Mathematics and Statistics, University of St Andrews, U. K.

Abstract

‎This paper concerns aspects of various graphs whose vertex set is a group $G$‎ ‎and whose edges reflect group structure in some way (so that‎, ‎in particular‎, ‎they are invariant under the action of the automorphism group of $G$)‎. ‎The‎ ‎particular graphs I will chiefly discuss are the power graph‎, ‎enhanced power‎ ‎graph‎, ‎deep commuting graph‎, ‎commuting graph‎, ‎and non-generating graph‎. ‎My main concern is not with properties of these graphs individually‎, ‎but ‎‎‎‎rather with comparisons between them‎. ‎The graphs mentioned‎, ‎together‎ ‎with the null and complete graphs‎, ‎form a hierarchy (as long as $G$ is‎ ‎non-abelian)‎, ‎in the sense that the edge set of any one is contained in that‎ ‎of the next; interesting questions involve when two graphs in the hierarchy‎ ‎are equal‎, ‎or what properties the difference between them has‎. ‎I also ‎‎‎consider various properties such as universality and forbidden subgraphs‎, ‎comparing how these properties play out in the different graphs‎. ‎I have also included some results on intersection graphs of subgroups of‎ ‎various types‎, ‎which are often in a ''dual'' relation to one of the other‎ ‎graphs considered‎. ‎Another actor is the Gruenberg--Kegel graph‎, ‎or prime graph‎, ‎of a group‎: ‎this very small graph has a surprising influence over various‎ ‎graphs defined on the group‎. ‎Other graphs which have been proposed‎, ‎such as the nilpotence‎, ‎solvability‎, ‎and Engel graphs‎, ‎will be touched on rather more briefly‎. ‎My emphasis is on‎ ‎finite groups but there is a short section on results for infinite groups‎. ‎There are briefer discussions of general $Aut(G)$-invariant graphs‎, ‎and structures other than groups (such as semigroups and rings)‎. ‎Proofs‎, ‎or proof sketches‎, ‎of known results have been included where possible‎. ‎Also‎, ‎many open questions are stated‎, ‎in the hope of stimulating further‎ ‎investigation‎. 

Keywords

Main Subjects


[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) PP. 18.
[2] J. Abawajy, A. Kelarev and M. Chowdhury, Power graphs: a survey, Elec. J. Graph Theory Appl., 1 (2013) 125–147.
[3] A. Abdollahi, Engel graph associated with a group, J. Algebra, 318 (2007) 680–691.
[4] A. Abdollahi, S. Akbari and H. R. Maimani, Noncommuting graph of a group, J. Algebra, 298 (2006) 468–492.
[5] A. Abdollahi and A. Mohammadi Hassanabadi, Noncyclic graph of a group, Commun. Algebra, 35 (2007) 2057–2081.
[6] A. Abdollahi and A. Mohammadi Hassanabadi, Non-cyclic graph associated with a group, J. Algebra Appl., 8 (2009)
243–257.
[7] A. Abdollahi and H. Shahverdi, Characterization of the alternating group by its non-commuting graph, J. Algebra,
357 (2012) 203–207.
[8] A. Abdollahi and Mohammed Zarrin, Non-nilpotent graph of a group, Commun. Algebra, 38 (2010) 4390–4403.
[9] M. Afkhami, M. Farrokhi and K. Khashyarmanesh, Planar, toroidal and projective commuting and noncommuting
graphs, Comm. Algebra, 43 (2015) 2964–2970.
[10] Karim Ahmadidelir, On the non-commuting graph in finite Moufang loops, J. Algebra Appl., 17 (2018).
[11] O. A. Alekseeva and A. S. Kondrat’ev, On recognizability of some finite simple orthogonal groups by spectrum,
Proc. Steklov Inst. Math., 266 (2009) 10–23.
[12] J. Araújo, M. Kinyon and J. Konieczny, Minimal paths in the commuting graphs of semigroups, Europ. J. Combi-
natorics, 32 (2011) 178–197.
[13] A. R. Ashrafi, A. Gholami and Z. Mehranian, Automorphism group of certain power graphs of finite groups, Elec-
tronic J. Graph Theory Appl., 5 (2017) 70–82.
[14] N. Ashrafi, H. R. Maimani, M. R. Pournaki and S. Yassemi, Unit graphs associated with rings, Commun. Algebra,
38 (2010) 2851–2871.
[15] R. Baer, Engelsche Elemente Noetherscher Gruppen, Math.Ann., 133 (1957) 256–270.
[16] R. A. Bailey, Association Schemes: Designed Experiments, Algebra and Combinatorics, Cambridge Studies in Ad-
vanced Mathematics, 84, Cambridge University Press, Cambridge, 2004.
[17] R. A. Bailey and Peter J. Cameron, Using graphs to find the best block designs, in Topics in Structural Graph
Theory (ed. L. W. Beineke and R. J. Wilson), Encyclopedia of Mathematics and its Applications, 147, Cambridge
University Press, Cambridge, (2013) 282–317.
[18] A. Ballester-Bolinches and R. Esteban-Romero, On minimal non-supersoluble groups, Rev. Mat. Iberoamericana, 23
(2007) 127–142.
[19] A. Ballester-Bolinches, R. Esteban-Romero and Derek J. S. Robinson, On finite minimal non-nilpotent groups, Proc.
Amer. Math. Soc., 133 (2005) 3455–3462.
[20] István Beck, Coloring of commutative rings, J. Algebra, 116 (1988) 208–226.
[21] J. L. Bell and A. B. Slomson, Models and Ultraproducts: An Introduction, Dover Publ., New York, 2006 (reprint of
1974 ed.)
[22] S. Bera, Hiranya Kishore Dey and Sajal Kumar Mukherjee, On the connectivity of enhanced power graphs of finite
groups, Graphs Combin., in press; doi: 10.1007/s00373-020-02267-5.
[23] S. R. Blackburn, P. M. Neumann and G. Venkataraman, Enumeration of Finite Groups, Cambridge Univ. Press,
Cambridge, 2007.
[24] A. Blass, G. Exoo and F. Harary, Paley graphs satisfy all first‐order adjacency axioms, J. Graph Theory, 5 (1981)
435–439.
[25] F. A. Bogomolov, The Brauer group of quotient spaces by linear group actions, Izv. Akad. Nauk SSSR Ser. Mat, 51
(1987) 485–516.
[26] B. Bollobás and A. Thomason, Graphs which contain all small graphs, Europ. J. Combinatorics, 2 (1981) 13–15.
[27] J. Bosák, The graphs of semigroups, Theory of Graphs and its Applications (Proc. Symp. Smolenice 1963), Academic
Press, New York, 1965 119–125.
[28] R. Brauer and K. A. Fowler, On groups of even order, Ann. Math., 62 (1955) 565–583.
[29] T. Breuer, R. M. Guralnick and W. M. Kantor, Probabilistic generation of finite simple groups II, J. Algebra, 320
(2008) 443–494.
[30] J. R. Britnell and N. Gill, Perfect commuting graphs, J. Group Theory, 20 (2017) 71–102.
31] T. C. Burness, R. M. Guralnick and S. Harper, The spread of a finite group, Ann. of Math. (2), 193 (2021) 619–687.

[32] Peter J. Cameron, Coherent configurations, association schemes, and permutation groups, Groups, combinatorics
and geometry (Durham, 2001), World Sci. Publ., River Edge, NJ, 2003 55–71.
Coherent configurations, association schemes and permutation groups. Groups, combinatorics and geometry
(Durham, 2001), 55–71, World Sci. Publ., River Edge, NJ, 2003.
[33] Peter J. Cameron, The power graph of a finite group, II, J. Group Theory, 13 (2010) 779–783.
[34] Peter J. Cameron, S. D. Freedman and C. M. Roney-Dougal, The non-commuting, non-generating graph of a
nilpotent group, Electronic J. Combinatorics, 28 (2021) pp. 15.
[35] Peter J. Cameron and S. Ghosh, The power graph of a finite group, Discrete Math., 311 (2011) 1220–1222.
[36] Peter J. Cameron, H. Guerra and S. Jurina, The power graph of a torsion-free group, J. Algebraic Combin., 49
(2019) 83–98.
[37] Peter J. Cameron and Sayyed Heidar Jafari, On the connectivity and independence number of power graphs of
groups, Graphs Combin., 36 (2020) 895–9904.
[38] Peter J. Cameron and Bojan Kuzma, Between the enhanced power graph and the commuting graph, https://
arxiv.org/2012.03789.
[39] Peter J. Cameron, A. Lucchini and Colva M. Roney-Dougal, Generating sets of finite groups, Trans. Amer. Math.
Soc., 370 (2018) 6751–6770.
[40] P. J. Cameron, P. Manna and R. Mehatari, Forbidden subgraphs of power graphs, https://arxiv.org/abs/2010.
05198.
[41] P. J. Cameron and N. Maslova, Criterion of unrecognizability of a finite group by its Gruenberg–Kegel graph,
https://arxiv.org/abs/2012.01482.
[42] T. T. Chelvam and M. Sattantathan, Subgroup intersection graph of finite abelian group, Trans. Com., 1 (2012)
5–10.
[43] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. Math., 164
(2006) 51–229.
[44] H. Cohn, Number Theory, Graduate Texts in Mathematics, 240, Springer, New York, 2007.
[45] J. Covington, A universal structure for N -free graphs, Proc. London Math. Soc. (3), 58 (1989) 1–16.
[46] Ch. Garnet Cox, On the spread of infinite groups, https://arxiv.org/abs/2012.12197.
[47] B. Csákány and G. Pollák, The graph of subgroups of a finite group. Czechoslovak Math. J., 19 (1969) 241–247.
[48] P. Diaconis and M. Simper, Statistical enumeration of groups by double cosets, https://arxiv.org/abs/2102.
04576.
[49] Robert P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math., 51 (1950) 161–166.
[50] S. Eberhard, Commuting probabilities of finite groups, Bull. London Math. Soc., 47 (2015) 796–808.
[51] G. Ellis, HAP, Homological Algebra Programming, Version 1.29 (2021), https://gap-packages.github.io/hap.
[52] M. Feng, X. Ma, and K. Wang, The full automorphism group of the power (di)graph of a finite group, Europ. J.
Combinatorics 52 (2016) 197–206. 
[53] S. D. Freedman, The intersection graph of a finite simple group has diameter at most 5, Arch. Math., in press; doi
10.1007/s00013-021-01583-3.
[54] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung., 18 (1967) 25–66.
[55] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.11.0; 2020, https://www.gap-system.
org.
[56] M. Giudici and C. W. Parker, There is no upper bound for the diameter of the commuting graph of a finite group,
J. Combinatorial Theory (A), 120 (2013) 1600–1603.
[57] G. Glauberman, Central elements in core-free groups, J. Algebra, 4 (1996) 403–420.
[58] C. D. Godsil, Association Schemes, https://www.math.uwaterloo.ca/~cgodsil/pdfs/assoc2.pdf.
[59] D. Gorenstein and J. H. Walter, The characterization of groups with dihedral 2-subgroups. III., J. Algebra, 2 (1965)
354–393.
[60] Robert L. Griess Jr., Schur multipliers of the known finite simple groups, Bull. Amer. Math. Soc., 78 (1972) 68–71.
[61] K. W. Gruenberg and K. W. Roggenkamp, Decomposition of the augmentation ideal and of the relation modules of
a finite group, Proc. London Math. Soc. (3), 31 (1975) 149–166.
[62] R. Guralnick, B. Kunyavskiĭ, E. Plotin and A. Shalev, Thompson-line characterization of the solvable radical, J.
Algebra 300 (2006) 363–375.
[63] R. M. Guralnick and G. R. Robinson, On the commuting probability in finite groups, J. Algebra, 300 (2006) 509–528.
[64] M. Hall, Jr., The Theory of Groups, Macmillan, New York, 1959.
[65] Z. Han, G. Chen and X. Guo, A characterization theorem for sporadic simple groups, Siberian Math. J., 49 (2008)
1138–1146.
[66] H. Hasanzadeh Bashir and K. Ahmadidelir, Some structural graph properties of the commuting graph of a class of
finite Moufang loops, Electronic J. Graph Theory Appl., 8 (2020) 319–337.
[67] Hamideh. Hasanzadeh Bashir and A. Iranmanesh, The intersection graph of a finite Moufang loop, J. Math. Exten-
sion, 14 (2020) 81–90.
[68] M. Herzog, P. Longobardi and M. Maj, On a graph related to the maximal subgroups of a group, Bull. Austral.
Math. Soc., 81 (2010) 317–328.
[69] G. Higman, Odd characterizations of finite simple groups, Lecture notes, University of Michigan, 1968 pp. 77.
[70] W. Hodges, A Shorter Model Theory, Cambridge Univ. Press, Cambridge, 1997.
[71] X. Huang, Q. Huang and S. M. Cioabă, The second eigenvalue of some normal Cayley graphs of high transitive
groups, Electronic J. Combinatorics, 26 (2019) pp. 26.
[72] A. Iranmanesh and A. A. Jafarzadeh, On the commuting graph associated with the symmetric and alternating
groups, J. Algebra Appl., 7 (2008) 129–146.
[73] , M. Jerrum, Computational Pólya theory, in Surveys in Combinatorics 1995 (ed. Peter Rowlinson), London Math.
Soc. Lecture Note Series, 218, Cambridge Univ. Press, Cambridge, (1995) 103–118.
[74] U. Jezernik and P. Moravec, Commutativity preserving extensions of groups, Proc. Roy. Soc. Edinburgh Sect. A,
148 (2018) 575–592.
[75] H. A. Jung, On a class of posets and the corresponding comparability graphs, J. Combinatorial Theory Ser. B, 24
(1978) 125–133.
[76] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of groups, (Proc. of the Vienna Confer-
ence, Vienna, 1999), Contrib. General Algebra, 12 (2000) 229–235.
[77] A. V. Kelarev and S. J. Quinn, Directed graph and combinatorial properties of semigroups, J. Algebra, 251 (2002)
16–26.
[78] 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 (2000) 294–302.
[79] B. E. Kunyavskiĭ, The Bogomolov multiplier of finite simple groups, In Cohomological and geometric approaches to
rationality problems, Progress in Mathematics, 282 (2010) 209–217.
[80] B. Larose, F. Laviolette and C. Tardif, On normal Cayley graphs and hom-independent graphs, Europ. J. Combi-
natorics, 19 (1998) 867–881.
[81] M. W. Liebeck and A. Shalev, Simple groups, probabilistic methods, and a conjectureof Kantor and Lubotzky, J.
Algebra, 184 (1996) 31–57.
[82] Y.-F. Lin, A problem of Bosák concerning the graphs of semigroups, Proc. Amer. Math. Soc., 21 (1969) 343–346.
[83] L. Lovász, Balanced hypergraphs and the Perfect Graph Conjecture, Discrete Math., 2 (1972) 253–267.
[84] A. Lucchini and A. Maróti, On the clique number of the generating graph of a finite group, Proc. Amer. Math. Soc.,
137 (2009) 3207–3217.
[85] A. Lucchini and D. Nemmi, The diameter of the non-nilpotent graph of a finite group, Trans. Comb., 9 (2020)
111–114.
[86] X. Ma, On the diameter of the intersection graph of a finite simple group, Czechoslovak Math. J., 66 (2016) 365–370.
[87] G. A. Miller and H. C. Moreno, Non-abelian groups in which every subgroup is abelian, Trans. Amer. Math. Soc.,
27 (1903) 398–404.
[88] G. L. Morgan and C. W. Parker, The diameter of the commuting graph of a finite group with trivial centre, J.
Algebra, 393 (2013) 41–59.
[89] G. Nagy and P. Vojtěchovský, The LOOPS package for GAP, https://gap-packages.github.io/loops/.
[90] J. A. Nelder, The analysis of randomized experiments with orthogonal block structure, I; Block structure and the
null analysis of variance, Proc. Royal Soc. London (A), 283 (1965) 147–162.
[91] B. H. Neumann, A problem of Paul Erdős on groups, J. Austral. Math. Soc. (A), 21 (1976) 467–472.
[92] D. Patrick and E. Wepsic, Cyclicizers, centralizers and normalizers, Tech. Report MS-TR 91-05, Rose-Hulman
Institute of Technology, IN, USA, 1991.
[93] B. Ponděliček, Diameter of a graph of a semigroup, Časposis Pěst. Mat., 92 (1967) 206–211.
[94] R. Rajkumar and P. Devi, Intersection graphs of cyclic subgroups of groups, Electronic Notes Discrete Math., 53
(2016) 15–24.
[95] G. Ravindra and K. R. Parthasarathy, Perfect product graphs, Discrete Math., 20 (1977) 177–186.
[96] B. Reed, A semi-strong perfect graph theorem, J. Combinatorial Theory (B), 43 (1987) 223–240.
[97] Derek J. S. Robinson, A Course in the Theory of Groups, (2nd edition), Springer, New York, 1996.
[98] O. Yu. Schmidt, Groups all of whose subgroups are nilpotent, Mat. Sbornik, (Russian), 31 (1924) 366–372.
[99] I. Schur, Über die Darstellung der endlichen Gruppen durch gebrochene lineare Substitutionen, J. reine angew.
Math., 127 (1904) 20–50.
[100] Y. Segev, The commuting graph of minimal nonsolvable groups, Geometriae Dedicata, 88 (2001) 55–66.
[101] D. Seinsche, On a property of the class of n-colorable graphs, J. Combinatorial Theory (B), 16 (1974) 191–193.
[102] R. Shen, Intersection graphs of subgroups of finite groups, Czechoslovak Math. J., 60 (2010) 945–950.
[103] Y. Shitov, Coloring the power graph of a semigroup, Graphs Combin., 33 (2017) 485–487.
[104] L. H. Soicher, The GRAPE package for GAP, Version 4.8.3, 2019, https://gap-packages.github.io/grape.
[105] R. M. Solomon and A. J. Woldar, Simple groups are characterized by their non-commuting graphs, J. Group Theory,
16 (2013) 793–824.
[106] T. P. Speed and R. A. Bailey, On a class of association schemes derived from lattices of equivalence relations, in:
ALgebraic Structures and Applications, (ed. P. Schulz, C. E. Praeger and R. P. Sullivan), M. Dekker, New York,
(1982) 55–74.
[107] D. P. Sumner, Dacey graphs, J. Aust. Math. Soc., 18 (1974) 492–502.
[108] J. G. Thompson, Nonsolvable finite groups all of whose local subgroups are solvable (Part I), Bull. Amer. Math.
Soc. (NS), 74 (1968) 383–437.
[109] D. L. Walker, Power Graphs of Quasigroups, Graduate thesis, University of South Florida, 2019; https://
scholarcommons.usf.edu/etd/7984.
[110] J. H. Walter, The characterization of finite groups with abelian Sylow 2-subgroups, Ann. Math., 89 (1969) 405–514.
[111] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.
[112] J. S. Williams, Prime graph components of finite groups, J. Algebra, 69 (1981) 487–513.
[113] R. A. Wilson, et al., Atlas of Finite Group Representations, version 3, http://brauer.maths.qmul.ac.uk/Atlas/
v3/.
[114] A. Woldar, A combinatorial approach to the character theory of split metabelian groups, J. Combinatorial Theory
(A), 50 (1989) 100–109.
[115] M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs Discrete Math., 182 (1998) 309–319.
[116] S. Zahirović, The power graph of a torsion-free group determines the directed power graph, https://arxiv.org/abs/
2006.01984.
[117] S. Zahirović, I. Bošnjak and R. Madarśz, A study of enhanced power graphs of finite groups, J. Algebra Appl., 19
(2020) pp. 20.
[118] M. Zorn, Nilpotency of finite groups, Bull. Amer. Math. Soc., 42 (1936) 485–486.