A NOTE ON K-4-CLOSURES IN HAMILTONIAN GRAPH-THEORY

Let G = (V, E) be a 2-connected graph. We call two vertices u and v of G a K4-pair if u and v are the vertices of degree two of an induced s ubgraph of G which is isomorphic to K4 minus an edge. Let x and y be t he common neighbors of a K4-pair u, v in an induced K4-e. We prove the following result: If N(x) or N(y) subset-or-equal-to N(u) or N(v) or {u,v}, then G is hamiltonian if and only if G + uv is hamiltonian. As a consequence, a claw-free graph G is hamiltonian if and only if G + u v is hamiltonian, where u, v is a K4-pair. Based on these results we d efine socalled K4-Closures of G. We give infinite classes of graphs wi th small maximum degree and large diameter, and with many vertices of degree two having complete K4-Closures.