Metraipolis › archive › dc_a9f751edccb7

Moore graph — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Moore_graph
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T22:33:01.672Z
SHA-256 of the archived text
131eeda3c91647b45f28555c99e816842e0851587347be27918e40420de8a0dd
Stable URL of this page
https://metraipolis.com/documento/dc_a9f751edccb7

How to cite

Moore graph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Moore_graph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_a9f751edccb7 (Metraipolis archive dc_a9f751edccb7, sha256 131eeda3c91647b45f28555c99e816842e0851587347be27918e40420de8a0dd)
BibTeX
@misc{dca9f751edccb7,
  title = {Moore graph — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Moore_graph},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_a9f751edccb7; sha256 131eeda3c91647b45f28555c99e816842e0851587347be27918e40420de8a0dd},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Moore_graph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is d and its diameter is k, its girth must equal 2k + 1. This is true, for a graph of degree d and diameter k, if and only if its number of vertices (its order) equals 1 + d ∑ i = 0 k − 1 ( d − 1 ) i , {\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i},} an upper bound on the largest possible number of vertices in any graph with this degree and diameter. Therefore, these graphs solve the degree diameter problem for their parameters. Another equivalent definition of a Moore graph G is that it has girth g = 2k + 1 and precisely n/g(m − n + 1) cycles of length g, where n and m are, respectively, the numbers of vertices and edges of G. They are in fact extremal with respect to the number of cycles whose length is the girth of the graph. Moore graphs were named by Hoffman & Singleton (1960) after Edward F. Moore, who posed the question of describing and classifying these graphs. Hoffman and Singleton showed that if the diameter is 2, then the degree must be 2, 3, 7, or 57. (All these graphs are strongly regular.) They also showed that if the diameter is 3 then G must be a 7-cycle. Later, Damerell (1973) proved that no Moore graphs exist with diameter greater than 2 apart from odd cycles. As well as having the maximum possible number of vertices for a given combination of degree and diameter, Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth. That is, any Moore graph is a cage. The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth as well as odd girth, and again these graphs are cages.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Moore graph» — https://en.wikipedia.org/wiki/Moore_graph
Wikidata Q3115522 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3115522
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Moore_graph?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1374109900, consultata il 2026-10-07T22:11:36.214Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0ed020d20516cc91581a74291e26c880f5950fdca0126341909f3830f903e4d8