# Heavy Subgraphs, Stability and Hamiltonicity

Discussiones Mathematicae Graph Theory (2017)

- Volume: 37, Issue: 3, page 691-710
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBinlong Li, and Bo Ning. "Heavy Subgraphs, Stability and Hamiltonicity." Discussiones Mathematicae Graph Theory 37.3 (2017): 691-710. <http://eudml.org/doc/288479>.

@article{BinlongLi2017,

abstract = {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.},

author = {Binlong Li, Bo Ning},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {heavy subgraphs; hamiltonian graphs; closure theory},

language = {eng},

number = {3},

pages = {691-710},

title = {Heavy Subgraphs, Stability and Hamiltonicity},

url = {http://eudml.org/doc/288479},

volume = {37},

year = {2017},

}

TY - JOUR

AU - Binlong Li

AU - Bo Ning

TI - Heavy Subgraphs, Stability and Hamiltonicity

JO - Discussiones Mathematicae Graph Theory

PY - 2017

VL - 37

IS - 3

SP - 691

EP - 710

AB - 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.

LA - eng

KW - heavy subgraphs; hamiltonian graphs; closure theory

UR - http://eudml.org/doc/288479

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.