Quartic graphs with minimum spectral gap

Abstract: Aldous and Fill conjectured that the maximum relaxation time for the random walk on a connected regular graph with

n

vertices is

(1 + o (1)) f r a c 3 n^{2} 2 p i^{2}

. This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected

k

-regular graph on

n

vertices is at least

(1 + o (1)) f r a c 2 k p i^{2} 3 n^{2}

, and the bound is attained for at least one value of

k

. We determine the structure of connected quartic graphs on

n

vertices with minimum spectral gap which enable us to show that the minimum spectral gap of connected quartic graphs on

n

vertices is

(1 + o (1)) f r a c 4 p i^{2} n^{2}

. From this result, the Aldous--Fill conjecture follows for

k = 4

.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Quartic graphs with minimum spectral gap