The Moore bound for irregular graphs
type: Item
instance of: scholarly article
title: The Moore bound for irregular graphs
zbMATH Open document ID: 0990.05075
author: Noga Alon
author: Shlomo Hoory
author: Nathan Linial
published in: Graphs and Combinatorics
publication date: 2002-05-14T00:00:00Z
review text: 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)]).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1740503
zbMATH Keywords: Moore bound
zbMATH Keywords: regular graph
reviewed by: William G. Brown
MaRDI profile type: Publication
full work available at URL: s003730200002
OpenAlex ID: W2058374373
DOI: 10.1007/S003730200002
Recommended article: An Entropy-Based Proof for the Moore Bound for Irregular Graphs
Recommended article: Q3474681
Recommended article: A Tight Bound on the Irregularity Strength of Graphs
Recommended article: A revised Moore bound for mixed graphs
Recommended article: A Spectral Moore Bound for Bipartite Semiregular Graphs
Recommended article: A New Upper Bound for the Irregularity Strength of Graphs
Recommended article: Some new spectral bounds for graph irregularity
Recommended article: On total regularity of mixed graphs with order close to the Moore bound
Recommended article: A spectral bound for graph irregularity
Recommended article: A note on the irregularity of graphs
description: scientific article; zbMATH DE number 1740503