Geodesic
The Ryjáček Closure and a Forbidden Subgraph
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 621-628.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2016_36_3_a7,
     author = {Saito, Akira and Xiong, Liming},
     title = {The {Ryj\'a\v{c}ek} {Closure} and a {Forbidden} {Subgraph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {621--628},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a7/}
}
TY  - JOUR
AU  - Saito, Akira
AU  - Xiong, Liming
TI  - The Ryjáček Closure and a Forbidden Subgraph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 621
EP  - 628
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a7/
LA  - en
ID  - DMGT_2016_36_3_a7
ER  - 
%0 Journal Article
%A Saito, Akira
%A Xiong, Liming
%T The Ryjáček Closure and a Forbidden Subgraph
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 621-628
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a7/
%G en
%F DMGT_2016_36_3_a7
Saito, Akira; Xiong, Liming. The Ryjáček Closure and a Forbidden Subgraph. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 621-628. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a7/

[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

[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

[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

[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

[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

[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

[9] C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309-324. doi:10.1002/jgt.3190100308