Sufficient spectral conditions for graphs being k-edge-Hamiltonian or k-Hamiltonian

DOI10.1080/03081087.2022.2093321zbMATH Open1529.05104arXiv2109.01973OpenAlexW3196328165WikidataQ114100547 ScholiaQ114100547MaRDI QIDQ6115877FDOQ6115877

Authors: Yongtao Li, Yuejian Peng 

Publication date: 10 August 2023

Published in: Linear and Multilinear Algebra (Search for Journal in Brave)

Abstract: A graph $G$ is $k$-edge-Hamiltonian if any collection of vertex-disjoint paths with at most $k$ edges altogether belong to a Hamiltonian cycle in $G$. A graph $G$ is $k$-Hamiltonian if for all $SsubseteqV(G)$ with $|S|lek$, the subgraph induced by $V(G)setminusS$ has a Hamiltonian cycle. These two concepts are classical extensions for the usual Hamiltonian graphs. In this paper, we present some spectral sufficient conditions for a graph to be $k$-edge-Hamiltonian and $k$-Hamiltonian in terms of the adjacency spectral radius as well as the signless Laplacian spectral radius. Our results could be viewed as slight extensions of the recent theorems proved by Li and Ning [Linear Multilinear Algebra 64 (2016)], Nikiforov [Czechoslovak Math. J. 66 (2016)] and Li, Liu and Peng [Linear Multilinear Algebra 66 (2018)]. Moreover, we shall prove a stability result for graphs being $k$-Hamiltonian, which could be regarded as a complement of two recent results of F"{u}redi, Kostochka and Luo [Discrete Math. 340 (2017)] and [Discrete Math. 342 (2019)].

Full work available at URL: https://arxiv.org/abs/2109.01973

zbMATH Keywords

stabilityHamiltonian cyclespectral radius

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Paths and cycles (05C38)

Cites Work

• On a conjecture of V. Nikiforov
• A sharp upper bound of the spectral radius of graphs
• On Hamilton's ideals
• Spectral analogues of Erdős’ and Moon–Moser’s theorems on Hamilton cycles
• Some Inequalities for the Largest Eigenvalue of a Graph
• On graphs with randomly deleted edges
• Sufficient spectral conditions on Hamiltonian and traceable graphs
• Spectral radius and Hamiltonian properties of graphs
• Spectral radius and Hamiltonicity of graphs
• Spectra of graphs
• Title not available (Why is that?)
• Graph theory with applications
• Some Theorems on Abstract Graphs
• The spectral radius of trees on \(k\) pendant vertices
• Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees
• A method in graph theory
• On Hamiltonian bipartite graphs
• Title not available (Why is that?)
• On three conjectures involving the signless Laplacian spectral radius of graphs
• Arc coverings of graphs
• Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs
• Graphs and matrices
• Spectral radius and Hamiltonicity of graphs with large minimum degree
• Variations on the Hamiltonian Theme
• Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph
• A stability version for a theorem of Erdős on nonhamiltonian graphs
• Generalization of a Theorem of Posa
• n-Hamiltonian graphs
• Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree
• Spectral results on Hamiltonian problem
• A variation of a theorem by Pósa
• Spectral conditions and Hamiltonicity of a balanced bipartite graph with large minimum degree
• Spectral radius and Hamiltonian properties of graphs, II
• Unified spectral Hamiltonian results of balanced bipartite graphs and complementary graphs
• Spectral conditions for graphs to be \(k\)-Hamiltonian or \(k\)-path-coverable
• Some generalizations of spectral conditions for 2s-hamiltonicity and 2s-traceability of bipartite graphs

Cited In (5)

• Title not available (Why is that?)
• Some sufficient spectral conditions on Hamilton-connected and traceable graphs
• Spectral conditions for graphs to be \(k\)-Hamiltonian or \(k\)-path-coverable
• Sufficient spectral radius conditions for Hamilton-connectivity of \(k\)-connected graphs
• On sufficient spectral radius conditions for Hamiltonicity of \(k\)-connected graphs

This page was built for publication: Sufficient spectral conditions for graphs being k-edge-Hamiltonian or k-Hamiltonian

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