Expander graphs and logarithmic diameter

465 Views Asked by At

It is well known that if a family of graphs $\{\Gamma_n\}_{n \geq 1}$ is an $(\epsilon)$-expander, then it has logarithmic diameter.

Do you know a family of connected $d$-regular graphs with logarithmic diameter, but not expander? I'm mainly interested in Cayley graphs, but this is not necessary.

1

There are 1 best solutions below

0
On BEST ANSWER
  1. A complete binary tree $T_N$ on $N$ vertices has logarithmic diameter but is not an expander, indeed removing 1 vertex disconnects the tree $T_n$ into two sets with $\frac{N-1}{2}$ vertices each. However $T_N$ is of course not a Cayley graph though.

  2. The hypercubic graph $H_n$ on $N=2^n$ vertices is Cayley has logarithmic diameter, but turns out not to be an expander. However, the degree of each vertex in $H_n$ is $n$ so the $H_n$s do not form an infinite family of bounded-degree graphs.

  3. As for an infinite family of graphs both bounded-degree and Cayley, that have logarithmic diameter but are not expanders, it turns out that yes indeed, there does exist such a family, but the answer was a research question:

https://www.sciencedirect.com/science/article/pii/S0195669805001733