Toughness, hamiltonicity and spectral radius in graphs

DOI10.1016/J.EJC.2023.103701arXiv2204.02257MaRDI QIDQ6395751FDOQ6395751

Authors: Dandan Fan, Huiqiu Lin, Hongliang Lu 

Publication date: 5 April 2022

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'{a}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 $ho(G)geqho(M_n)$, then $G$ contains a hamiltonian cycle, unless $Gcong{M}_n$, where $M_n=K_{1}abla{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)>fracdlambda-1$ where $lambda$ 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 $delta$ and to be $t$-tough, respectively.

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Eulerian and Hamiltonian graphs (05C45)

This page was built for publication: Toughness, hamiltonicity and spectral radius in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6395751)