The Ryjáček Closure and a Forbidden Subgraph

• Autorzy: Akira Saito , Liming Xiong
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

closure; claw-free graph; Hamiltonian graph; perfect matching; traceable graph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 621-628

Daty

wydano

2016-08-01

otrzymano

2015-05-29

poprawiono

2015-09-30

zaakceptowano

2015-09-30

online

2016-07-06

Twórcy

autor

Akira Saito

• Department of Information Science Nihon University Sakurajosui 3–25–40 Setagaya-Ku, Tokyo 156–8550, Japan

autor

Liming Xiong

• School of Mathematics and Statistics Beijing Institute of Technology Beijing 100081, China and Beijing Key Laboratory on MCAACI Beijing Institute of Technology Beijing 100081, China

Bibliografia

• [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]
• [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]
• [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]
• [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]
• [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]
• [9] C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309-324. doi:10.1002/jgt.3190100308[Crossref]

Identyfikatory

DOI

10.7151/dmgt.1876