PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 621-628
Tytuł artykułu

The Ryjáček Closure and a Forbidden Subgraph

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
3
Strony
621-628
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2015-05-29
poprawiono
2015-09-30
zaakceptowano
2015-09-30
online
2016-07-06
Twórcy
autor
  • Department of Information Science Nihon University Sakurajosui 3–25–40 Setagaya-Ku, Tokyo 156–8550, Japan, asaito@chs.nihon-u.ac.jp
autor
  • 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, lmxiong@bit.edu.cn
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1876
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.