The Ryjáček Closure and a Forbidden Subgraph
Discussiones Mathematicae Graph Theory (2016)
- Volume: 36, Issue: 3, page 621-628
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topAkira Saito, and Liming Xiong. "The Ryjáček Closure and a Forbidden Subgraph." Discussiones Mathematicae Graph Theory 36.3 (2016): 621-628. <http://eudml.org/doc/285522>.
@article{AkiraSaito2016,
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.},
author = {Akira Saito, Liming Xiong},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {closure; claw-free graph; Hamiltonian graph; perfect matching; traceable graph},
language = {eng},
number = {3},
pages = {621-628},
title = {The Ryjáček Closure and a Forbidden Subgraph},
url = {http://eudml.org/doc/285522},
volume = {36},
year = {2016},
}
TY - JOUR
AU - Akira Saito
AU - Liming Xiong
TI - The Ryjáček Closure and a Forbidden Subgraph
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 621
EP - 628
AB - 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.
LA - eng
KW - closure; claw-free graph; Hamiltonian graph; perfect matching; traceable graph
UR - http://eudml.org/doc/285522
ER -
References
top- [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] Zbl0665.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] Zbl0536.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] Zbl0424.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] Zbl1070.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] Zbl0338.05118
- [9] C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309-324. doi:10.1002/jgt.3190100308[Crossref]
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.