PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 1 | 137-143
Tytuł artykułu

A note on a new condition implying pancyclism

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to $K_{n/2,n/2}$.
Słowa kluczowe
Wydawca
Rocznik
Tom
21
Numer
1
Strony
137-143
Opis fizyczny
Daty
wydano
2001
otrzymano
2000-11-15
poprawiono
2000-12-13
Twórcy
  • LRI, Bât. 490, Université de Paris-Sud, 91405 Orsay, France
autor
  • LRI, Bât. 490, Université de Paris-Sud, 91405 Orsay, France
  • Faculty of Applied Mathematics AGH, Al. Mickiewicza 30, 30-059 Kraków, Poland
  • Faculty of Applied Mathematics AGH, Al. Mickiewicza 30, 30-059 Kraków, Poland
Bibliografia
  • [1] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
  • [2] J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-136, doi: 10.1016/0012-365X(76)90078-9.
  • [3] J.A. Bondy and U.S.A. Murty, Graph Theory with Applications (Elsevier, North Holland, New York, 1976).
  • [4] V. Chvátal, On Hamilton's ideals, J. Combin. Theory 12 (B) (1972) 163-168.
  • [5] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69.
  • [6] G.H. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory (B) 37 (1984) 221-227, doi: 10.1016/0095-8956(84)90054-6.
  • [7] R. Faudree, O. Favaron, E. Flandrin and H. Li, Pancyclism and small cycles in graphs, Discuss. Math. Graph Theory 16 (1996) 27-40, doi: 10.7151/dmgt.1021.
  • [8] O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
  • [9] 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.
  • [10] Z. Skupień, private communication.
  • [11] R. Zhu, Circumference in 2-connected graphs, Qu-Fu Shiyuan Xuebao 4 (1983) 8-9.
  • [12] L. Zhenhong, G. Jin and C. Wang, Two sufficient conditions for pancyclic graphs, Ars Combinatoria 35 (1993) 281-290.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1138
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ć.