Dirac's minimum degree condition restricted to claws (Q1356453): Difference between revisions

A graph \(G\) of order \(n\) is 1-heavy (2-heavy) if at least one (two) of the end vertices of each induced claw \(K_{1,3}\) has degree at leat \(n/2\). It is shown that if \(G\) is a 2-connected 2-heavy graph of order \(n\geq 3\) such that \(|N(u)\cup N(v)|\geq 2\) for each pair of vertices \(u\) and \(v\) with \(d(u,v)=2\) and \(\max\{d(u),d(v)\}< n/2\), then \(G\) is Hamiltonian. This generalizes several known Hamiltonian results, including the result of Shi. Other forms of the result are also proved; for example, ``2-connected and 2-heavy'' can be replaced by ``3-connected and 1-heavy'' without changing the conclusion that the graph is Hamiltonian. Results on the relationship between the previously mentioned conditions and toughness and the existence of perfect matchings are also proved.