Some localization theorems on Hamiltonian circuits

Given the graph G, denote by \(M^ k(u)\) and N(u) the sets of all \(v\in V(G)\) with d(u,v)\(\leq k\) and \(d(u,v)=1\), respectively. Earlier [the authors, Math. Notes 35, 33-35 (1984); translation from Math. Zametki 35, No.1, 55-61 (1984; Zbl 0552.05038)] the authors had proven a `localization' variant of Posa's hamiltonicity theorem. The same is done here for the theorems of Dirac, Ore and \textit{G.-H. Fan} [J. Comb. Theory, Ser. B 37, 221-227 (1984; Zbl 0551.05048)]. It is shown that if G is a connected graph with at least three vertices and if \(d(u)+d(v)\geq | N(u)+N(v)+N(w)|\) for each triple of vertices u, v, w with \(d(u,v)=2\) and \(w\in N(u)\cap N(v)\), then G is hamiltonian. As another example the authors prove that if G is a 2-connected graph of order p and \(d(u)<p/2,\) \(d(u,v)=2\Rightarrow d(v)\geq | M^ 3(u)| /2\) whenever u and v are distinct vertices of G, then G is hamiltonian.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Some localization theorems on Hamiltonian circuits

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