Closure and forbidden pairs for Hamiltonicity (Q1403925)

From MaRDI portal
Revision as of 16:35, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
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