The Ryjáček Closure and a Forbidden Subgraph

Abstract

The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.

Keywords

• closure
• claw-free graph
• hamiltonian graph
• perfect matching
• traceable graph