Prime graph

In the mathematics of graph theory and finite groups, a prime graph is an undirected graph defined from a group. These graphs were introduced in a 1981 paper by J. S. Williams, credited to unpublished work from 1975 by K. W. Gruenberg and O. Kegel.^[1]

Definition

The prime graph of a group has a vertex for each prime number that divides the order (number of elements) of the given group, and an edge connecting each pair of prime numbers $p$ and $q$ for which there exists a group element with order $pq$ .^[1]^[2]

Equivalently, there is an edge from $p$ to $q$ whenever the given group contains commuting elements of order $p$ and of order $q$ ,^[1] or whenever the given group contains a cyclic group of order $pq$ as one of its subgroups.^[2]

Properties

Certain finite simple groups can be recognized by the degrees of the vertices in their prime graphs.^[3] The connected components of a prime graph have diameter at most five, and at most three for solvable groups.^[4] When a prime graph is a tree, it has at most eight vertices, and at most four for solvable groups.^[5]

Related graphs

Variations of prime graphs that replace the existence of a cyclic subgroup of order $pq$ , in the definition for adjacency in a prime graph, by the existence of a subgroup of another type, have also been studied.^[2] Similar results have also been obtained from a related family of graphs, obtained from a finite group through the degrees of its characters rather than through the orders of its elements.^[6]

References

^ ^a ^b ^c Williams, J. S. (1981), "Prime graph components of finite groups", Journal of Algebra, 69 (2): 487–513, doi:10.1016/0021-8693(81)90218-0, MR 0617092
^ ^a ^b ^c Abe, Seiichi; Iiyori, Nobuo (2000), "A generalization of prime graphs of finite groups", Hokkaido Mathematical Journal, 29 (2): 391–407, doi:10.14492/hokmj/1350912979, MR 1776716
^ Moghaddamfar, A. R.; Zokayi, A. R.; Darafsheh, M. R. (2005), "A characterization of finite simple groups by the degrees of vertices of their prime graphs", Algebra Colloquium, 12 (3): 431–442, doi:10.1142/S1005386705000398, MR 2144997
^ Lucido, Maria Silvia (1999), "The diameter of the prime graph of a finite group", Journal of Group Theory, 2 (2): 157–172, doi:10.1515/jgth.1999.011, MR 1681526, Zbl 0921.20020
^ Lucido, Maria Silvia (2002), "Groups in which the prime graph is a tree", Bollettino della Unione Matematica Italiana, 5 (1): 131–148, MR 1881928, Zbl 1097.20022
^ Tong-Viet, Hung P. (2013), "Groups whose prime graphs have no triangles", Journal of Algebra, 378: 196–206, arXiv:1303.3457, doi:10.1016/j.jalgebra.2012.12.024, MR 3017021, S2CID 119118934

[williams-1] Williams, J. S. (1981), "Prime graph components of finite groups", Journal of Algebra, 69 (2): 487–513, doi:10.1016/0021-8693(81)90218-0, MR 0617092

[cyclic-2] Abe, Seiichi; Iiyori, Nobuo (2000), "A generalization of prime graphs of finite groups", Hokkaido Mathematical Journal, 29 (2): 391–407, doi:10.14492/hokmj/1350912979, MR 1776716

[degrees-3] Moghaddamfar, A. R.; Zokayi, A. R.; Darafsheh, M. R. (2005), "A characterization of finite simple groups by the degrees of vertices of their prime graphs", Algebra Colloquium, 12 (3): 431–442, doi:10.1142/S1005386705000398, MR 2144997

[diam-4] Lucido, Maria Silvia (1999), "The diameter of the prime graph of a finite group", Journal of Group Theory, 2 (2): 157–172, doi:10.1515/jgth.1999.011, MR 1681526, Zbl 0921.20020

[tree-5] Lucido, Maria Silvia (2002), "Groups in which the prime graph is a tree", Bollettino della Unione Matematica Italiana, 5 (1): 131–148, MR 1881928, Zbl 1097.20022

[character-6] Tong-Viet, Hung P. (2013), "Groups whose prime graphs have no triangles", Journal of Algebra, 378: 196–206, arXiv:1303.3457, doi:10.1016/j.jalgebra.2012.12.024, MR 3017021, S2CID 119118934

[1]

[2]

[3]

[4]

[5]

[6]