An entropy based proof of the Moore bound for irregular graphs

Details An entropy based proof of the Moore bound for irregular graphs An entropy based proof of the Moore bound for irregular graphs

2010-11-04

arxiv.org/abs/1011.1058v1

Computer Science

Discrete Mathematics

6 pages

Scientific paper

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}

Affiliated with

Also associated with

No associations

Rating

An entropy based proof of the Moore bound for irregular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An entropy based proof of the Moore bound for irregular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An entropy based proof of the Moore bound for irregular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-145317