PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 120 | 1 | 63-75
Tytuł artykułu

A note on the Song-Zhang theorem for Hamiltonian graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds:
(i) there exist u ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G);
(ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ S},
then G is Hamiltonian. We prove that if for each essential independent set S of cardinality k+1, one of conditions (i) or (ii) holds, then G is Hamiltonian. A number of known results on Hamiltonian graphs are corollaries of this result.
Słowa kluczowe
Rocznik
Tom
120
Numer
1
Strony
63-75
Opis fizyczny
Daty
wydano
2010
Twórcy
autor
  • Department of Mathematics, Qiongzhou University, Sanya, Hainan 572022, P.R. China
  • Deptartment of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, U.S.A.
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_4064-cm120-1-5
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ć.