PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2000 | 20 | 2 | 165-172
Tytuł artykułu

2-factors in claw-free graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced $K_{1,3}$.) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.
Słowa kluczowe
Kategorie tematyczne
Wydawca
Rocznik
Tom
20
Numer
2
Strony
165-172
Opis fizyczny
Daty
wydano
2000
otrzymano
1999-02-19
poprawiono
2000-01-24
Twórcy
autor
  • Georgia State University, Atlanta, GA 30303
  • University of Alaska Fairbanks, Fairbanks, AK 99775
  • Emory University, Atlanta, GA 30322
autor
  • Nihon University, Tokyo 156, Japan
Bibliografia
  • [1] J.A. Bondy, Pancyclic Graphs I, J. Combin. Theory (B) 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
  • [2] S. Brandt, G. Chen, R.J. Faudree, R.J. Gould and L. Lesniak, On the Number of Cycles in a 2-Factor, J. Graph Theory, 24 (1997) 165-173, doi: 10.1002/(SICI)1097-0118(199702)24:2<165::AID-JGT4>3.3.CO;2-A
  • [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman and Hall, London, 3rd edition, 1996).
  • [4] R.J. Gould, Updating the Hamiltonian Problem - A Survey, J. Graph Theory 15 (1991) 121-157, doi: 10.1002/jgt.3190150204.
  • [5] M.M. Matthews and D.P. Sumner, Longest Paths and Cycles in $K_{1,3}$-Free Graphs, J. Graph Theory 9 (1985) 269-277, doi: 10.1002/jgt.3190090208.
  • [6] O. Ore, Hamiltonian Connected Graphs, J. Math. Pures. Appl. 42 (1963) 21-27.
  • [7] H. Li and C. Virlouvet, Neighborhood Conditions for Claw-free Hamiltonian Graphs, Ars Combinatoria 29 (A) (1990) 109-116.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1116
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ć.