PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 1 | 47-54
Tytuł artykułu

Forbidden triples implying Hamiltonicity: for all graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with $G_i = K_{1,3}$ for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁, G₂, G₃ such that all G₁G₂G₃-free graphs are hamiltonian.
Słowa kluczowe
Wydawca
Rocznik
Tom
24
Numer
1
Strony
47-54
Opis fizyczny
Daty
wydano
2004
otrzymano
2001-03-15
poprawiono
2003-04-25
Twórcy
  • University of Memphis, Memphis, TN 38152, USA
  • Emory University, Atlanta, GA 30322, USA
  • University of Colorado at Denver, Denver, CO 80217, USA
Bibliografia
  • [1] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity (Ph.D. Thesis, Memphis State University, 1991).
  • [2] J. Brousek, Forbidden Triples and Hamiltonicity, Discrete Math. 251 (2002) 71-76, doi: 10.1016/S0012-365X(01)00326-0.
  • [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (3rd Edition, Chapman & Hall, 1996).
  • [4] R.J. Faudree and R.J. Gould, Characterizing Forbidden Pairs for Hamiltonian Properties, Discrete Math. 173 (1997) 45-60, doi: 10.1016/S0012-365X(96)00147-1.
  • [5] R.J. Faudree, R.J. Gould and M.S. Jacobson, Potential Forbidden Triples Implying Hamiltonicity: For Sufficiently Large Graphs, preprint.
  • [6] R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak, Characterizing Forbidden Clawless Triples for Hamiltonian Graphs, Discrete Math. 249 (2002) 71-81, doi: 10.1016/S0012-365X(01)00235-7.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1212
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ć.