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 [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] for which there exists a group element with order [math]\displaystyle{ pq }[/math].[1][2]
Equivalently, there is an edge from [math]\displaystyle{ p }[/math] to [math]\displaystyle{ q }[/math] whenever the given group contains commuting elements of order [math]\displaystyle{ p }[/math] and of order [math]\displaystyle{ q }[/math],[1] or whenever the given group contains a cyclic group of order [math]\displaystyle{ pq }[/math] 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 [math]\displaystyle{ pq }[/math], 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
- ↑ 1.0 1.1 1.2 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
- ↑ 2.0 2.1 2.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, http://projecteuclid.org/euclid.hokmj/1350912979
- ↑ 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
- ↑ "The diameter of the prime graph of a finite group", Journal of Group Theory 2 (2): 157–172, 1999, doi:10.1515/jgth.1999.011
- ↑ "Groups in which the prime graph is a tree", Bollettino della Unione Matematica Italiana 5 (1): 131–148, 2002
- ↑ Tong-Viet, Hung P. (2013), "Groups whose prime graphs have no triangles", Journal of Algebra 378: 196–206, doi:10.1016/j.jalgebra.2012.12.024
 |  |
