PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2016 | 14 | 1 | 19-28
Tytuł artykułu

Hamilton cycles in almost distance-hereditary graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H). Adopting the terminology introduced by Broersma et al. and Čada, a graph G is called 1-heavy if at least one of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has degree at least n/2, and is called claw-heavy if each claw of G has a pair of end vertices with degree sum at least n. In this paper we prove the following two theorems: (1) Every 2-connected, claw-heavy and almost distance-hereditary graph is Hamiltonian. (2) Every 3-connected, 1-heavy and almost distance-hereditary graph is Hamiltonian. The first result improves a previous theorem of Feng and Guo [J.-F. Feng and Y.-B. Guo, Hamiltonian cycle in almost distance-hereditary graphs with degree condition restricted to claws, Optimazation 57 (2008), no. 1, 135–141]. For the second result, its connectedness condition is sharp since Feng and Guo constructed a 2-connected 1-heavy graph which is almost distance-hereditary but not Hamiltonian.
Wydawca
Czasopismo
Rocznik
Tom
14
Numer
1
Strony
19-28
Opis fizyczny
Daty
wydano
2016-01-01
otrzymano
2015-08-04
zaakceptowano
2015-10-27
online
2016-02-09
Twórcy
autor
  • Department of Applied Mathematics, School of Science, Xi’an University of Technology, Xi’an, Shaanxi 710048, P.R.
autor
  • Center for Applied Mathematics, Tianjin University, Tianjin, 300072, P.R., bo.ning@tju.edu.cn
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_1515_math-2016-0003
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ć.