×

Chvátal-Erdős type theorems. (English) Zbl 1214.05069

Summary: The Chvátal-Erdős theorems imply that if \(G\) is a graph of order \(n\geq 3\) with \(\kappa(G)\geq\alpha(G)\), then \(G\) is Hamiltonian, and if \(\kappa(G)>\alpha(G)\), then \(G\) is Hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if \(G\) is a graph of order \(n\) and \(k\geq 2\) is a positive integer such that \(\kappa(G)\geq k\), \(\delta(G)> (n+ k^2- k)/(k+ 1)\), and \(\delta(G)\geq\alpha(G)+ k- 2\), then \(G\) is Hamiltonian. It is shown that if \(G\) is a graph of order \(n\) and \(k\geq 3\) is a positive integer such that \(\kappa(G)\geq 4k^2+ 1\), \(\delta(G)> (n+ k^2- 2k)/k\), and \(\delta(G)\geq\alpha(G)+ k- 2\), then \(G\) is Hamiltonian-connected. This result supports the conjecture that if \(G\) is a graph of order \(n\) and \(k\geq 3\) is a positive integer such that \(\kappa(G)\geq k\), \(\delta(G)> (n_ k^2- 2k)/k\), and \(\delta(G)\geq\alpha(G)+ k- 2\), then \(G\) is Hamiltonian-connected, and the conjecture is verified for \(k= 3\) and \(4\).

MSC:

05C45 Eulerian and Hamiltonian graphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI Link