Toughness, hamiltonicity and spectral radius in graphs. (May 2023)

• Record Type: Journal Article
• Authors: Fan, Dandan; Lin, Huiqiu; Lu, Hongliang
• Is Part Of: European journal of combinatorics. Volume 110(2023)
• Publication Date: 2023-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2023.103701
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: The study of the existence of Hamiltonian cycles in a graph is a classical 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 ρ ( G ) ≥ ρ ( M n ), then G contains a Hamiltonian cycle, unless G ≅ M n, where M n = K 1 ∇ K n − 4 + 3 and K n − 4 + 3 is the graph obtained from 3 K 1 ∪ K n − 4 by adding three independent edges between 3 K 1 and K n − 4 . The Brouwer's toughness theorem states that every d -regular connected graph always has t ( G ) > d λ − 1 where λ 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 δ and to be t -tough, respectively.