PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 3 | 691-710
Tytuł artykułu

Heavy Subgraphs, Stability and Hamiltonicity

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let G be a graph. Adopting the terminology of Broersma et al. and Čada, respectively, we say that G is 2-heavy if every induced claw (K1,3) of G contains two end-vertices each one has degree at least |V (G)|/2; and G is o-heavy if every induced claw of G contains two end-vertices with degree sum at least |V (G)| in G. In this paper, we introduce a new concept, and say that G is S-c-heavy if for a given graph S and every induced subgraph G′ of G isomorphic to S and every maximal clique C of G′, every non-trivial component of G′ − C contains a vertex of degree at least |V (G)|/2 in G. Our original motivation is a theorem of Hu from 1999 that can be stated, in terms of this concept, as every 2-connected 2-heavy and N-c-heavy graph is hamiltonian, where N is the graph obtained from a triangle by adding three disjoint pendant edges. In this paper, we will characterize all connected graphs S such that every 2-connected o-heavy and S-c-heavy graph is hamiltonian. Our work results in a different proof of a stronger version of Hu’s theorem. Furthermore, our main result improves or extends several previous results.
Słowa kluczowe
Wydawca
Rocznik
Tom
37
Numer
3
Strony
691-710
Opis fizyczny
Daty
wydano
2017-08-01
otrzymano
2015-06-22
poprawiono
2016-02-05
zaakceptowano
2016-06-11
online
2017-07-06
Twórcy
autor
  • , , Xi’an, , P.R.
  • , Pilsen, Czech Republic
autor
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1967
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ć.