Spectral radius and Hamiltonicity of graphs with large minimum degree

DOI10.1007/S10587-016-0301-YzbMATH Open1413.05242arXiv1602.01033OpenAlexW2964234038MaRDI QIDQ2828825FDOQ2828825

Vladimir Nikiforov

Publication date: 26 October 2016

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

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$.

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

zbMATH Keywords

Hamiltonian cycleHamiltonian pathminimum degreespectral radius

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (30)

• Spectral analogues of Erdős' theorem on Hamilton-connected graphs
• Some generalizations of spectral conditions for 2s-hamiltonicity and 2s-traceability of bipartite graphs
• Signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree
• Spectral radius and Hamiltonicity of graphs
• The \(Q\)-index and connectivity of graphs
• Spectral results on Hamiltonian problem
• Spectral conditions and Hamiltonicity of a balanced bipartite graph with large minimum degree
• A sufficient \(Q\)-spectral condition for a graph to be \(\beta\)-deficient involving minimum degree
• Sufficient spectral conditions for graphs being k-edge-Hamiltonian or k-Hamiltonian
• The largest eigenvalue conditions for Hamiltonian and traceable graphs
• Spectral radius and Hamiltonian properties of graphs, II
• Bounds on signless Laplacian eigenvalues of Hamiltonian graphs
• Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius
• Some spectral sufficient conditions for a graph being pancyclic
• Some new sufficient conditions for 2p-Hamilton-biconnectedness of graphs
• Laplacian spread and some Hamiltonian properties of 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
• Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree
• Sufficient conditions for Hamilton-connected graphs in terms of (signless Laplacian) spectral radius
• Spectral conditions for graphs to be β-deficient involving minimum degree
• Spectral radius and \(k\)-connectedness of a graph
• On sufficient spectral radius conditions for Hamiltonicity
• Spectral radius and traceability of graphs with large minimum degree
• The spectral radius and \(k\)-power of Hamilton cycle of graphs
• The number of edges, spectral radius and Hamilton-connectedness of graphs
• Spectral radius and Hamiltonian properties of graphs
• The spectral radius and \({\mathcal{P}}_{\ge \ell}\)-factors of graphs involving minimum degree
• Spectral conditions for some graphical properties

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)