Toughness, hamiltonicity and spectral radius in graphs

Abstract

The study of the existence of hamiltonian cycles in a graph is a classic problem in graph theory. By incorporating toughness and spectral conditions, we can consider Chvátal's conjecture from another perspective: what is the spectral condition to guarantee the existence of a hamiltonian cycle among $t$-tough graphs? We first give the answer to $1$-tough graphs, i.e. if $\ddot{I}(G)\ge \ddot{I}(M_n)$, then $G$ contains a hamiltonian cycle, unless $G\cong M_n$, where $M_n=K_1\nabla K_{n-4}^{+3}$ and $K_{n-4}^{+3}$ is the graph obtained from $3K_1\cup K_{n-4}$ by adding three independent edges between $3K_1$ and $K_{n-4}$. The Brouwer's toughness theorem states that every $d$-regular connected graph always has $t(G)>\frac{d}{\hat{I}}»-1$ where $\hat{I}»$ is the second largest absolute eigenvalue of the adjacency matrix. In this paper, we extend the result in terms of its spectral radius, i.e. we provide a spectral condition for a graph to be 1-tough with minimum degree $\hat{I}´$ and to be $t$-tough, respectively.

13 pages