The Moore bound for irregular graphs (Q1348665): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
m rollbackEdits.php mass rollback
Tag: Rollback
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s003730200002 / rank
Normal rank
 
Property / OpenAlex ID
 
Property / OpenAlex ID: W2058374373 / rank
Normal rank
 

Revision as of 14:08, 20 March 2024

scientific article
Language Label Description Also known as
English
The Moore bound for irregular graphs
scientific article

    Statements

    The Moore bound for irregular graphs (English)
    0 references
    0 references
    0 references
    0 references
    14 May 2002
    0 references
    The Moore bound for the minimum number \(n_0(d,g)\) of vertices in a regular graph of prescribed girth [see \textit{A. J. Hoffman} and \textit{R. R. Singleton}, On Moore graphs with diameters 2 and 3. IBM J. Res. Dev. 4, 497-504 (1960; Zbl 0096.38102) and \textit{P. Erdős} and \textit{H. Sachs}, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl (Regular graphs with given girth and minimal number of knots) (German), Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 12, 251-258 (1963; Zbl 0116.15002)] ``arises from the fact (that) the ball of radius \(\lfloor\frac{g-1}2\rfloor\) around a vertex or an edge (depending on the parity of \(g\)) is a tree.'' Let \(n(d,g)\) denote the the minimum number of vertices in a graph of girth \(g\) and average degree \(\geq d\). Theorem 1. \(n(d,g)\geq n_0(d,g)\) (cf.\ Problem 10, p.\ 163 in [\textit{B. Bollobás}, Extremal graph theory (L. M. S. Monographs. 11. London, New York, San Francisco: Academic Press) (1978; Zbl 0419.05031)]).
    0 references
    Moore bound
    0 references
    regular graph
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references