Prime graph
{{short description|Undirected graph defined from a group}}
{{about|graphs defined from finite groups|other uses|Glossary of graph theory#prime}}
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.{{r|williams}}
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 and for which there exists a group element with order .{{r|williams|cyclic}}
Equivalently, there is an edge from to whenever the given group contains commuting elements of order and of order ,{{r|williams}} or whenever the given group contains a cyclic group of order as one of its subgroups.{{r|cyclic}}
Properties
Certain finite simple groups can be recognized by the degrees of the vertices in their prime graphs.{{r|degrees}} The connected components of a prime graph have diameter at most five, and at most three for solvable groups.{{r|diam}} When a prime graph is a tree, it has at most eight vertices, and at most four for solvable groups.{{r|tree}}
Related graphs
Variations of prime graphs that replace the existence of a cyclic subgroup of order , in the definition for adjacency in a prime graph, by the existence of a subgroup of another type, have also been studied.{{r|cyclic}} 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.{{r|character}}
References
{{reflist|refs=
| last1 = Abe | first1 = Seiichi
| last2 = Iiyori | first2 = Nobuo
| doi = 10.14492/hokmj/1350912979
| issue = 2
| journal = Hokkaido Mathematical Journal
| mr = 1776716
| pages = 391–407
| title = A generalization of prime graphs of finite groups
| volume = 29
| year = 2000| url = http://projecteuclid.org/euclid.hokmj/1350912979
}}
| last = Tong-Viet | first = Hung P.
| doi = 10.1016/j.jalgebra.2012.12.024
| journal = Journal of Algebra
| mr = 3017021
| pages = 196–206
| title = Groups whose prime graphs have no triangles
| volume = 378
| year = 2013| s2cid = 119118934
| arxiv = 1303.3457
}}
| last1 = Moghaddamfar | first1 = A. R.
| last2 = Zokayi | first2 = A. R.
| last3 = Darafsheh | first3 = M. R.
| doi = 10.1142/S1005386705000398
| issue = 3
| journal = Algebra Colloquium
| mr = 2144997
| pages = 431–442
| title = A characterization of finite simple groups by the degrees of vertices of their prime graphs
| volume = 12
| year = 2005}}
| last = Lucido | first = Maria Silvia | author-link = Maria Silvia Lucido
| doi = 10.1515/jgth.1999.011
| issue = 2
| journal = Journal of Group Theory
| mr = 1681526
| pages = 157–172
| title = The diameter of the prime graph of a finite group
| volume = 2
| year = 1999
| zbl = 0921.20020}}
| last = Lucido | first = Maria Silvia | author-link = Maria Silvia Lucido
| issue = 1
| journal = Bollettino della Unione Matematica Italiana
| mr = 1881928
| pages = 131–148
| title = Groups in which the prime graph is a tree
| volume = 5
| year = 2002
| zbl = 1097.20022}}
| last = Williams | first = J. S.
| doi = 10.1016/0021-8693(81)90218-0
| issue = 2
| journal = Journal of Algebra
| mr = 617092
| pages = 487–513
| title = Prime graph components of finite groups
| volume = 69
| year = 1981| doi-access = free
}}
}}