A degree sum condition for long cycles passing through a linear forest

Jun Fujisawa; Tomoki Yamashita

doi:10.1016/j.disc.2007.05.005

A degree sum condition for long cycles passing through a linear forest

Jun Fujisawa
, Tomoki Yamashita

研究成果: Article › 査読

1 被引用数 (Scopus)

抄録

Let G be a (k + m)-connected graph and F be a linear forest in G such that | E (F) | = m and F has at most k - 2 components of order 1, where k ≥ 2 and m ≥ 0. In this paper, we prove that if every independent set S of G with | S | = k + 1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min { d - m, | V (G) | } which contains all the vertices and edges of F.

本文言語	English
ページ（範囲）	2382-2388
ページ数	7
ジャーナル	Discrete Mathematics
巻	308
号	12
DOI	https://doi.org/10.1016/j.disc.2007.05.005
出版ステータス	Published - 2008 6月 28
外部発表	はい

ASJC Scopus subject areas

理論的コンピュータサイエンス
離散数学と組合せ数学

文献へのアクセス

10.1016/j.disc.2007.05.005

他のファイルとリンク

引用スタイル

@article{a23710ebfe6241479fa4b0f126952659,

title = "A degree sum condition for long cycles passing through a linear forest",

abstract = "Let G be a (k + m)-connected graph and F be a linear forest in G such that | E (F) | = m and F has at most k - 2 components of order 1, where k ≥ 2 and m ≥ 0. In this paper, we prove that if every independent set S of G with | S | = k + 1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min \{ d - m, | V (G) | \} which contains all the vertices and edges of F.",

keywords = "Degree sum, Linear forest, Long cycle",

author = "Jun Fujisawa and Tomoki Yamashita",

note = "Funding Information: This work was partially supported by the JSPS Research Fellowships for Young Scientists (to J.F.) and by the 21st Century COE Program; Integrative Mathematical Sciences: Progress in Mathematics Motivated by Social and Natural Sciences (to T.Y.).",

year = "2008",

month = jun,

day = "28",

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

language = "English",

volume = "308",

pages = "2382--2388",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - A degree sum condition for long cycles passing through a linear forest

AU - Fujisawa, Jun

AU - Yamashita, Tomoki

N1 - Funding Information: This work was partially supported by the JSPS Research Fellowships for Young Scientists (to J.F.) and by the 21st Century COE Program; Integrative Mathematical Sciences: Progress in Mathematics Motivated by Social and Natural Sciences (to T.Y.).

PY - 2008/6/28

Y1 - 2008/6/28

N2 - Let G be a (k + m)-connected graph and F be a linear forest in G such that | E (F) | = m and F has at most k - 2 components of order 1, where k ≥ 2 and m ≥ 0. In this paper, we prove that if every independent set S of G with | S | = k + 1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min { d - m, | V (G) | } which contains all the vertices and edges of F.

AB - Let G be a (k + m)-connected graph and F be a linear forest in G such that | E (F) | = m and F has at most k - 2 components of order 1, where k ≥ 2 and m ≥ 0. In this paper, we prove that if every independent set S of G with | S | = k + 1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min { d - m, | V (G) | } which contains all the vertices and edges of F.

KW - Degree sum

KW - Linear forest

KW - Long cycle

UR - https://www.scopus.com/pages/publications/41549131212

UR - https://www.scopus.com/pages/publications/41549131212#tab=citedBy

U2 - 10.1016/j.disc.2007.05.005

DO - 10.1016/j.disc.2007.05.005

M3 - Article

AN - SCOPUS:41549131212

SN - 0012-365X

VL - 308

SP - 2382

EP - 2388

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

ER -

A degree sum condition for long cycles passing through a linear forest

抄録

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル