Spectral radius and Hamiltonicity of graphs with large minimum degree.

DOI10.1007/S10587-016-0301-YMaRDI QIDQ2828825zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov

Publication date 26 October 2016

Published in Czechoslovak Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.01033, http://hdl.handle.net/10338.dmlcz/145880

zbMATH Keywords

Hamiltonian cycleHamiltonian pathminimum degreespectral radius

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: This paper presents sufficient conditions for Hamiltonian paths and cycles in graphs. Letting $lambdaleft(Gight)$ denote the spectral radius of the adjacency matrix of a graph $G,$ the main results of the paper are: (1) Let $kgeq1,$ $ngeq{k}^3/2+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft(Gight)geqk.$ If [ lambdaleft( G ight) geq n-k-1, ] then $G$ has a Hamiltonian cycle, unless $G=K_{1}vee(K_{n-k-1}+K_k)$ or $G=K_{k}vee(K_{n-2k}+overline{K}_k)$. (2) Let $kgeq1,$ $ngeq{k}^3/2+k^2/2+k+5,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft(Gight)geqk.$ If [ lambdaleft( G ight) geq n-k-2, ] then $G$ has a Hamiltonian path, unless $G=K_{k}vee(K_{n-2k-1}+overline{K}_{k+1})$ or $G=K_{n-k-1}+K_{k+1}$ In addition, it is shown that in the above statements, the bounds on $n$ are tight within an additive term not exceeding $2$.

Recommendations

• Spectral radius and Hamiltonian properties of graphs
• Spectral radius and Hamiltonicity of graphs
• Spectral radius and Hamiltonicity of graphs
• Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree
• On sufficient spectral radius conditions for Hamiltonicity of \(k\)-connected graphs

Cites work

• A method in graph theory
• A sharp upper bound of the spectral radius of graphs
• Arc coverings of graphs
• Hamilton connected graphs
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Laplacian spectral radius and some Hamiltonian properties of graphs
• On Hamilton's ideals
• Signless Laplacian spectral radius and Hamiltonicity
• Small spectral gap in the combinatorial Laplacian implies Hamiltonian
• Some Inequalities for the Largest Eigenvalue of a Graph
• Some Theorems on Abstract Graphs
• Sparse pseudo‐random graphs are Hamiltonian
• Spectral condition for Hamiltonicity of a graph
• Spectral radius and Hamiltonian graphs
• Spectral radius and Hamiltonian properties of graphs
• Spectral radius and Hamiltonicity of graphs
• Sufficient spectral conditions on Hamiltonian and traceable graphs

Cited in

(41)

• Spectral radius and \(k\)-connectedness of a graph
• The number of edges, spectral radius and Hamilton-connectedness of graphs
• Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree
• Spectral results on Hamiltonian problem
• Spectral analogues of Erdős' theorem on Hamilton-connected graphs
• Spectral conditions and Hamiltonicity of a balanced bipartite graph with large minimum degree
• Bounds on signless Laplacian eigenvalues of Hamiltonian graphs
• Sufficient spectral radius conditions for Hamilton-connectivity of \(k\)-connected graphs
• Spectral radius and the 2-power of Hamilton cycle
• The spectral radius and \({\mathcal{P}}_{\ge \ell}\)-factors of graphs involving minimum degree
• Some spectral sufficient conditions for a graph being pancyclic
• On sufficient spectral radius conditions for Hamiltonicity of \(k\)-connected graphs
• Spectral conditions for graphs to be \(k\)-Hamiltonian or \(k\)-path-coverable
• Sufficient conditions for Hamilton-connected graphs in terms of (signless Laplacian) spectral radius
• A sufficient \(Q\)-spectral condition for a graph to be \(\beta\)-deficient involving minimum degree
• On sufficient spectral radius conditions for Hamiltonicity
• Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles
• scientific article; zbMATH DE number 5116216 (Why is no real title available?)
• Spectral conditions for graphs to be \(\beta\)-deficient involving minimum degree
• Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius
• Spectral radius and Hamiltonian properties of graphs
• Laplacian spread and some Hamiltonian properties of graphs
• Some new sufficient conditions for 2p-Hamilton-biconnectedness of graphs
• Some generalizations of spectral conditions for \(2s\)-Hamiltonicity and \(2s\)-traceability of bipartite graphs
• Spectral radius and Hamiltonian properties of graphs. II
• Spectral radius and traceability of graphs with large minimum degree
• Spectral conditions for some graphical properties
• Spectral radius of a balanced bipartite graph and its Hamiltonicity
• Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree
• The largest eigenvalue conditions for Hamiltonian and traceable graphs
• Spectral radius and Hamiltonicity of graphs
• Spectral radius and Hamiltonicity of graphs
• Sufficient spectral conditions for graphs being k-edge-Hamiltonian or k-Hamiltonian
• The spectral radius and \(k\)-power of Hamilton cycle of graphs
• The \(Q\)-index and connectivity of graphs
• Spectral radius and rainbow Hamilton paths of a graph
• Spectral radius and Hamiltonicity in split graphs
• Maxima of the Q-index: forbidden rainbow Hamilton paths, matchings and linear forests
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)

This page was built for publication: Spectral radius and Hamiltonicity of graphs with large minimum degree.

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