In the mathematics of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

and

finite group In abstract algebra, a finite group is a group whose underlying set is finite. Finite groups often arise when considering symmetry of mathematical or physical objects, when those objects admit just a finite number of structure-preserving tra ...

s, a prime graph is an

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

defined from a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...

. 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.

Definition

The prime graph of a group has a vertex for each prime number that divides the

order Order, ORDER or Orders may refer to: * A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica * Categorization, the process in which ideas and objects are recognized, differentiated, and understood ...

(number of elements) of the given group, and an

edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

connecting each pair of prime numbers

p

and

q

for which there exists a group element with order

pq

. Equivalently, there is an edge from

p

q

whenever the given group contains commuting elements of order

p

and of order

q

, or whenever the given group contains a

cyclic group In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...

of order

pq

as one of its subgroups.

Properties

Certain

finite simple group In mathematics, the classification of finite simple groups states that every finite simple group is cyclic, or alternating, or in one of 16 families of groups of Lie type, or one of 26 sporadic groups. The list below gives all finite simple g ...

s can be recognized by the degrees of the vertices in their prime graphs. The connected components of a prime graph have

diameter In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

at most five, and at most three for

solvable group In mathematics, more specifically in the field of group theory, a solvable group or soluble group is a group that can be constructed from abelian groups using extensions. Equivalently, a solvable group is a group whose derived series terminat ...

s. When a prime graph is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

, it has at most eight vertices, and at most four for solvable groups.

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. Similar results have also been obtained from a related family of graphs, obtained from a finite group through the degrees of its

characters Character or Characters may refer to: Arts, entertainment, and media Literature * ''Character'' (novel), a 1936 Dutch novel by Ferdinand Bordewijk * ''Characters'' (Theophrastus), a classical Greek set of character sketches attributed to Theoph ...

rather than through the orders of its elements.

References

{{reflist, refs= {{citation , 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 {{citation , 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 {{citation , 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 {{citation , 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 {{citation , 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 {{citation , 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 Application-specific graphs Finite groups