Abstract
Let G be a graph on n vertices. A vertex of G with degree at least n/2 is called a heavy vertex, and a cycle of G which contains all the heavy vertices of G is called a heavy cycle. In this note, we characterize graphs which contain no heavy cycles. For a given graph H, we say that G is H-heavy if every induced subgraph of G isomorphic to H contains two nonadjacent vertices with degree sum at least n. We find all the connected graphs S such that a 2-connected graph G being S'-heavy implies any longest cycle of G is a heavy cycle.
Original language | English |
---|---|
Pages (from-to) | 383-392 |
Number of pages | 10 |
Journal | Discussiones Mathematicae - Graph Theory |
Volume | 36 |
Issue number | 2 |
DOIs | |
State | Published - 2016 |
Keywords
- Heavy cycles
- Heavy subgraphs