Heavy subgraph conditions for longest cycles to be heavy in graphs

2011/09/21 by Binlong Li, Li, Binlong, Shenggui Zhang +1
Mathematics · #05C38 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C38

paper · pdf · doi:10.48550/arxiv.1109.4675

arxiv created 2011/09/21 · arxiv updated 2011/09/23

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 paper, we characterize the 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.

Related

• Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs
• Closures and heavy pairs for hamiltonicity
• Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs
• Large cycles in 4-connected graphs
• Hamilton and long cycles in t-tough graphs with t>1