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

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

Authors: S. Ajesh Babu, Jaikumar Radhakrishnan 

Publication date: 22 September 2016

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

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}

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

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

zbMATH Keywords

graphsgirthMoore bound

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Algebraic Graph Theory
• An upper bound on the number of Steiner triple systems
• An entropy proof of Bregman's theorem
• The Moore bound for irregular graphs
• Entropy, independent sets and antichains: A new approach to Dedekind's problem
• 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)