Forbidden subgraphs for longest cycles to contain vertices with large degrees

Binlong Li; Shenggui Zhang

doi:10.1016/j.disc.2014.07.003

Forbidden subgraphs for longest cycles to contain vertices with large degrees

Binlong Li, Shenggui Zhang

School of Mathematics and Statistics

Northwestern Polytechnical University Xian

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

Abstract Let G be a graph. For a given graph H, we say that G is H-free if G contains no copies of H as an induced subgraph. Suppose that G is 2-connected, has n vertices, and α is a real number with 0≤α≤1. In this paper, we characterize the connected graphs R such that G being R-free implies that every longest cycle of G passes through all vertices with degree at least αn+O(1) in G.

Original language	English
Article number	9899
Pages (from-to)	1681-1689
Number of pages	9
Journal	Discrete Mathematics
Volume	338
Issue number	10
DOIs	https://doi.org/10.1016/j.disc.2014.07.003
State	Published - 31 May 2015

Keywords

Forbidden subgraphs
Longest cycles
Stars

Access to Document

10.1016/j.disc.2014.07.003

Cite this

@article{f62fd95ffc764bc792c66cf99eef9a65,

title = "Forbidden subgraphs for longest cycles to contain vertices with large degrees",

abstract = "Abstract Let G be a graph. For a given graph H, we say that G is H-free if G contains no copies of H as an induced subgraph. Suppose that G is 2-connected, has n vertices, and α is a real number with 0≤α≤1. In this paper, we characterize the connected graphs R such that G being R-free implies that every longest cycle of G passes through all vertices with degree at least αn+O(1) in G.",

keywords = "Forbidden subgraphs, Longest cycles, Stars",

author = "Binlong Li and Shenggui Zhang",

note = "Publisher Copyright: {\textcopyright} 2014 Elsevier B.V.",

year = "2015",

month = may,

day = "31",

doi = "10.1016/j.disc.2014.07.003",

language = "英语",

volume = "338",

pages = "1681--1689",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "10",

}

TY - JOUR

T1 - Forbidden subgraphs for longest cycles to contain vertices with large degrees

AU - Li, Binlong

AU - Zhang, Shenggui

PY - 2015/5/31

Y1 - 2015/5/31

N2 - Abstract Let G be a graph. For a given graph H, we say that G is H-free if G contains no copies of H as an induced subgraph. Suppose that G is 2-connected, has n vertices, and α is a real number with 0≤α≤1. In this paper, we characterize the connected graphs R such that G being R-free implies that every longest cycle of G passes through all vertices with degree at least αn+O(1) in G.

AB - Abstract Let G be a graph. For a given graph H, we say that G is H-free if G contains no copies of H as an induced subgraph. Suppose that G is 2-connected, has n vertices, and α is a real number with 0≤α≤1. In this paper, we characterize the connected graphs R such that G being R-free implies that every longest cycle of G passes through all vertices with degree at least αn+O(1) in G.

KW - Forbidden subgraphs

KW - Longest cycles

KW - Stars

UR - http://www.scopus.com/inward/record.url?scp=84930081366&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2014.07.003

DO - 10.1016/j.disc.2014.07.003

M3 - 文章

AN - SCOPUS:84930081366

SN - 0012-365X

VL - 338

SP - 1681

EP - 1689

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

M1 - 9899

ER -

Forbidden subgraphs for longest cycles to contain vertices with large degrees

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this