Frage

Consider the family of graphs of degree $6$ with vertex set $V_n=(a, b, c)$ for all $0\leq a, b, c \leq n-1$ with $(a,b,c)$ being connected to $(a-1, b, c),(a+1, b,c), (a, b-1, c), (a, b+1, c), (a,b,c-1), (a,b, c+1)$, with all operations modulo $n$. Show that this is not a family of expander graphs.

I've been struggling with this question for over a week. I tried looking at from the algebraic perspective and show that the spectral gap is getting smaller as n(the number of vertexes) rise. But I got stuck a long the way and now I don't know if I'm on the right track at all.

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top