Name
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} |
Year | Venue | Keywords |
|---|---|---|
2010 | Clinical Orthopaedics and Related Research | bipartite graph,random walk,discrete mathematics |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Moore graph,Graph power,Vertex (geometry),Random walk,Biregular graph,Bipartite graph,Moore bound,Mathematics | Journal | abs/1011.1 |
Citations | PageRank | References |
1 | 0.38 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ajesh Babu | 1 | 7 | 1.20 |
| Jaikumar Radhakrishnan | 2 | 1123 | 96.04 |