Closure and Hamiltonian-connectivity of claw-free graphs Original Research Article

In Ryjáček (1997), the closure cl(G) for a claw-free graph G is defined, and it is proved that G is hamiltonian if and only if cl(G) is hamiltonian. On the other hand, there exist infinitely many claw-free graphs G such that G is not hamiltonian-connected (resp. homogeneously traceable) while cl(G) is hamiltonian-connected (resp. homogeneously traceable). In this paper we define a new closure clk(G) (k ⩾ 1) as a generalization of cl(G) and prove the following theorems. (1) A claw-free graph G is hamiltonian-connected if and only if cl3(G) is hamiltonian-connected. (2) A claw-free graph G is homogeneously traceable if and only if cl2(G) is homogeneously traceable. We also discuss the uniqueness of the closure.