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

MaRDI QIDQ5210982zbMATH OpenFDO

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

Publication date 17 January 2020

Full work available at URL https://arxiv.org/abs/1804.01258, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p53

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

zbMATH Keywords

Hamilton cycledegree sum condition

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(3)

• A short proof of a theorem concerning degree sums and connectivity on Hamiltonian graphs
• Hamiltonicity of 4-connected 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)