Closure and forbidden pairs for Hamiltonicity (Q1403925)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Closure and forbidden pairs for Hamiltonicity
scientific article

    Statements

    Closure and forbidden pairs for Hamiltonicity (English)
    0 references
    0 references
    20 August 2003
    0 references
    It was shown in [\textit{Z. Ryjáček}, Discrete Math. 164, 257-263 (1997; Zbl 0872.05044)] that the forbidden pairs \(R\) and \(S\) of connected graphs that imply a sufficiently large \(2\)-connected graph \(G\) is Hamiltonian are \(R = C\), the claw, and \(S\) a subgraph of \(P_6, Z_3, W\), the wounded, or \(N\), the net. In the present paper it is shown that the claw-free closure of all of these \(RS\)-free graphs form a subclass of the class of \(CN\)-free graphs. Thus, the determination of forbidden pairs of connected graphs that imply a graph is Hamiltonian can be reduced to the consideration of \(CN\)-free graphs. Also, the structure of the closure of \(CN\)-free graphs is completely determined.
    0 references
    Closure
    0 references
    Hamiltonian
    0 references
    Forbidden Pairs
    0 references

    Identifiers