Strengthening the closure concept in claw-free graphs (Q5936017): Difference between revisions

In 1997 \textit{Z. Ryjáček} [J. Comb. Theory, Ser. B 70, No. 2, 217-224 (1997; Zbl 0872.05032)] defined the closure \(\text{cl}(G)\) of a claw-free graph \(G\) by repeated applications of a local completion which consisted of adding all missing edges to the neighbourhood \(N(x)\) of a vertex \(x\), if \(N(x)\) induces a connected graph. In the present paper a new closure concept, the cycle closure \(\text{cl}_C(G)\) of a claw-free graph \(G\) is defined by repeated applications of the above closure operation \(\text{cl}\) and a so-called \(C\)-completion which consists of adding all missing edges to the closed neighbourhood of specific cycles. As for the closure \(\text{cl}\), the two main features of the cycle closure \(\text{cl}_C\) are that it is uniquely determined and does not change the length of a longest cycle. Furthermore, an infinite class of graphs \(G\) of order \(n\) and size \(\frac{3}{2}n-1\) is presented for which \(\text{cl}_C(G)\) is complete but not \(\text{cl}(G)\), i.e. the graphs are shown to be hamiltonian by \(\text{cl}_C\) but not by \(\text{cl}\).