Heavy Subgraph Conditions for Longest Cycles to Be Heavy in Graphs

• Autorzy: Binlong Lia , Shenggui Zhang
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

heavy cycles; heavy subgraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 2
• Strony: 383-392

Daty

wydano

2016-05-01

otrzymano

2015-02-18

poprawiono

2015-07-13

zaakceptowano

2015-07-13

online

2016-04-15

Twórcy

autor

Binlong Lia

• Department of Applied Mathematics Northwestern Polytechnical University Xi′an, Shaanxi 710072, P.R. China
• European Centre of Excellence NTIS 306 14 Plzeň, Czech Republic

autor

Shenggui Zhang

• Department of Applied Mathematics Northwestern Polytechnical University Xi′an, Shaanxi 710072, P.R. China

Identyfikatory

DOI

10.7151/dmgt.1863