An Entropy-Based Proof for the Moore Bound for Irregular Graphs

DOI10.1007/978-3-319-05446-9_10zbMATH Open1345.05048OpenAlexW1791758941MaRDI QIDQ2821702FDOQ2821702

Authors S. Ajesh Babu, Jaikumar Radhakrishnan 

Publication date 22 September 2016

Published in Perspectives in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.1058

zbMATH Keywords

graphsgirthMoore bound

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random walks on graphs (05C81)

Abstract: We provide proofs of the following theorems by considering the entropy of random walks: Theorem 1.(Alon, Hoory and Linial) Let G be an undirected simple graph with n vertices, girth g, minimum degree at least 2 and average degree d: Odd girth: If g=2r+1,then n geq 1 + d*(Sum_{i=0}^{r-1}(d-1)^i) Even girth: If g=2r,then n geq 2*(Sum_{i=0}^{r-1} (d-1)^i) Theorem 2.(Hoory) Let G = (V_L,V_R,E) be a bipartite graph of girth g = 2r, with n_L = |V_L| and n_R = |V_R|, minimum degree at least 2 and the left and right average degrees d_L and d_R. Then, n_L geq Sum_{i=0}^{r-1}(d_R-1)^{i/2}(d_L-1)^{i/2} n_R geq Sum_{i=0}^{r-1}(d_L-1)^{i/2}(d_R-1)^{i/2}

Recommendations

• The Moore bound for irregular graphs
• A Tight Bound on the Irregularity Strength of Graphs
• A lower bound on graph entropy
• Publication:3474681
• A new upper bound for the irregularity strength of graphs
• An entropic proof of cutoff on Ramanujan graphs
• A revised Moore bound for mixed graphs
• A Spectral Moore Bound for Bipartite Semiregular Graphs
• Hypergraphs, entropy, and inequalities
• Some new spectral bounds for graph irregularity

Cites Work

• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• Algebraic Graph Theory
• An entropy proof of Bregman's theorem
• An upper bound on the number of Steiner triple systems
• Entropy, independent sets and antichains: A new approach to Dedekind's problem
• The Moore bound for irregular graphs
• The size of bipartite graphs with a given girth

Cited In (1)

• The Moore bound for irregular graphs

This page was built for publication: An Entropy-Based Proof for the Moore Bound for Irregular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2821702)