A spectral lower bound for the treewidth of a graph and its consequences

We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a d-dimensional hypercube is at least ⌊3·2^d/(2(d+4))⌋−1. The currently known upper bound is . We generalize this result to Hamming graphs. We also observe that every graph G on n vertices, with maximum degree Δ

(1)

contains an induced cycle (chordless cycle) of length at least 1+log_Δ(μn/8) (provided G is not acyclic),

(2)

has a clique minor K_h for some ,

where μ is the second smallest eigenvalue of the Laplacian matrix of G.