Jump to content

Prime graph

From Wikipedia, the free encyclopedia

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

[edit]

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 .[1][2]

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

Properties

[edit]

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]

[edit]

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

[edit]
  1. ^ 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
  2. ^ 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
  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