A degree sum condition on the order, the connectivity and the independence number for Hamiltonicity

zbMATH Open1431.05089arXiv1804.01258MaRDI QIDQ5210982FDOQ5210982

Authors: Shuya Chiba, Michitaka Furuya, Kenta Ozeki, Masao Tsugaki, Tomoki Yamashita 

Publication date: 17 January 2020

Abstract: In [Graphs Combin.~24 (2008) 469--483.], the third author and the fifth author conjectured that if $G$ is a $k$-connected graph such that $sigm{a}_{k+1}(G)ge|V(G)|+kappa(G)+(k-2)(alpha(G)-1)$, then $G$ contains a Hamiltonian cycle, where $sigm{a}_{k+1}(G)$, $kappa(G)$ and $alpha(G)$ are the minimum degree sum of $k+1$ independent vertices, the connectivity and the independence number of $G$, respectively. In this paper, we settle this conjecture. This is an improvement of the result obtained by Li: If $G$ is a $k$-connected graph such that $sigm{a}_{k+1}(G)ge|V(G)|+(k-1)(alpha(G)-1)$, then $G$ is Hamiltonian. The degree sum condition is best possible.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Degree sum condition for \(k\)-ordered Hamiltonian connected graphs
• A degree sum condition concerning the connectivity and the independence number of a graph
• scientific article; zbMATH DE number 2170416
• Degree sum conditions for Hamiltonicity on \(k\)-partite graphs
• Degree conditions for k‐ordered hamiltonian graphs
• scientific article; zbMATH DE number 2065936
• A short proof of a theorem concerning degree sums and connectivity on Hamiltonian graphs
• A degree condition for Hamiltonian digraphs
• A degree sum condition for Hamiltonicity in balanced bipartite digraphs
• scientific article; zbMATH DE number 68362

zbMATH Keywords

Hamilton cycledegree sum condition

Mathematics Subject Classification ID

Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40)

Cites Work

• Graph theory
• Note on Hamilton Circuits
• Some Theorems on Abstract Graphs
• A note on Hamiltonian circuits
• A degree sum condition concerning the connectivity and the independence number of a graph
• A generalization of a result of Häggkvist and Nicoghossian
• Cycles through prescribed vertices with large degree sum
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• An improvement of fraisse's sufficient condition for hamiltonian graphs
• A remark on two sufficient conditions for Hamilton cycles

Cited In (3)

• Hamiltonicity of 4-connected graphs
• A short proof of a theorem concerning degree sums and connectivity on Hamiltonian graphs
• A degree sum condition concerning the connectivity and the independence number of a graph

This page was built for publication: A degree sum condition on the order, the connectivity and the independence number for Hamiltonicity

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