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.
@article{bwmeta1.element.doi-10_7151_dmgt_1876,
author = {Akira Saito and Liming Xiong},
title = {The Ryj\'a\v cek Closure and a Forbidden Subgraph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {621-628},
zbl = {1339.05219},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1876}
}
Akira Saito; Liming Xiong. The Ryjáček Closure and a Forbidden Subgraph. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 621-628. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1876/
[1] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs (5th Ed.) (Chapman and Hall/CRC, Boca Raton, Florida, USA, 2010).
[2] M. Jünger, W.R. Pulleyblank and G. Reinelt, On partitioning the edges of graphs into connected subgraphs, J. Graph Theory 9 (1985) 539-549. doi:10.1002/jgt.3190090416[Crossref] | Zbl 0665.05040
[3] M. Las Vergnas, A note on matchings in graphs, Colloque sur la Théorie des Graphes, Cahiers Centre Études Rech. Opér. 17 (1975) 257-260.
[4] M.M. Matthews and D.P. Sumner, Hamiltonian results in K1 , 3-free graphs, J. Graph Theory 8 (1984) 139-146. doi:10.1002/jgt.3190080116[Crossref] | Zbl 0536.05047
[5] D.J. Oberly and D.P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian, J. Graph Theory 3 (1979) 351-356. doi:10.1002/jgt.3190030405[Crossref] | Zbl 0424.05036
[6] M.D. Plummer and A. Saito, Forbidden subgraphs and bounds on the size of a max- imum matching, J. Graph Theory 50 (2005) 1-12. doi:10.1002/jgt.20087[Crossref] | Zbl 1070.05070
[7] Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224. doi:10.1006/jctb.1996.1732[Crossref]
[8] D.P. Sumner, 1-factors and antifactor sets, J. Lond. Math. Soc. (2) 13 (1976) 351-359. doi:10.1112/jlms/s2-13.2.351[Crossref] | Zbl 0338.05118
[9] C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309-324. doi:10.1002/jgt.3190100308[Crossref]