Heavy subgraph conditions for longest cycles to be heavy in graphs

Binlong Li, Henggui Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish
Pages (from-to)383-392
Number of pages10
JournalDiscussiones Mathematicae - Graph Theory
Volume36
Issue number2
DOIs
StatePublished - 2016

Keywords

  • Heavy cycles
  • Heavy subgraphs

Fingerprint

Dive into the research topics of 'Heavy subgraph conditions for longest cycles to be heavy in graphs'. Together they form a unique fingerprint.

Cite this