Misplaced Pages

Prime graph

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Undirected graph defined from a group This article is about graphs defined from finite groups. For other uses, see 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.

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 {\displaystyle p} and q {\displaystyle q} for which there exists a group element with order p q {\displaystyle pq} .

Equivalently, there is an edge from p {\displaystyle p} to q {\displaystyle q} whenever the given group contains commuting elements of order p {\displaystyle p} and of order q {\displaystyle q} , or whenever the given group contains a cyclic group of order p q {\displaystyle pq} as one of its subgroups.

Properties

Certain finite simple groups can be recognized by the degrees of the vertices in their prime graphs. The connected components of a prime graph have diameter at most five, and at most three for solvable groups. When a prime graph is a tree, 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 p q {\displaystyle 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 rather than through the orders of its elements.

References

  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
  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
  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
  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
  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
  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
Categories:
Prime graph Add topic