PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1996 | 16 | 1 | 27-40
Tytuł artykułu

Pancyclism and small cycles in graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (d_C(u,v)+1, [(n+19)/13]), $d_C(u,v)$ being the distance of u and v on a hamiltonian cycle of G.
Słowa kluczowe
Kategorie tematyczne
Wydawca
Rocznik
Tom
16
Numer
1
Strony
27-40
Opis fizyczny
Daty
wydano
1996
otrzymano
1995-11-03
Twórcy
  • Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA
  • L.R.I., URA 410 du C.N.R.S. Bât. 490, Université de Paris-sud, 91405-Orsay cedex, France.
  • L.R.I., URA 410 du C.N.R.S. Bât. 490, Université de Paris-sud, 91405-Orsay cedex, France.
autor
  • L.R.I., URA 410 du C.N.R.S. Bât. 490, Université de Paris-sud, 91405-Orsay cedex, France.
Bibliografia
  • [1] D. Amar, E. Flandrin, I. Fournier and A. Germa, Pancyclism in hamiltonian graphs, Discrete Math. 89 (1991) 111-131, doi: 10.1016/0012-365X(91)90361-5.
  • [2] A. Benhocine and A. P. Wojda, The Geng-Hua Fan conditions for pancyclic or hamilton-connected graphs, J. Combin. Theory (B) 42 (1987) 167-180, doi: 10.1016/0095-8956(87)90038-4.
  • [3] J.A. Bondy, Pancyclic graphs. I., J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
  • [4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan Press, 1976).
  • [5] R. Faudree, O. Favaron, E. Flandrin and H. Li, The complete closure of a graph, J. Graph Theory 17 (1993) 481-494, doi: 10.1002/jgt.3190170406.
  • [6] E.F. Schmeichel and S.L. Hakimi, Pancyclic graphs and a conjecture of Bondy and Chvátal, J. Combin. Theory (B) 17 (1974) 22-34, doi: 10.1016/0095-8956(74)90043-4.
  • [7] E.F. Schmeichel and S.L. Hakimi, A cycle structure theorem for hamiltonian graphs, J. Combin. Theory (B) 45 (1988) 99-107, doi: 10.1016/0095-8956(88)90058-5.
  • [8] R.H. Shi, The Ore-type conditions on pancyclism of hamiltonian graphs, personal communication.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1021
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ć.