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

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