Degree sums and dominating cycles

Yueyu Wu; Yaojun Chen; T. C.Edwin Cheng

doi:10.1016/j.disc.2020.112224

Degree sums and dominating cycles

Yueyu Wu, Yaojun Chen, T. C.Edwin Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

2 Citations (Scopus)

Abstract

A cycle C of a graph G is dominating if any vertex of V(G)∖V(C) has at least one neighbor on C and V(G)∖V(C) is an independent set. Let G be a k-connected graph of order n≥3 with k≥2. In this paper, we show that every longest cycle of G is dominating if the degree sums is more than (k+1)(n+1)∕3 for any k+1 pairwise nonadjacent vertices, and the lower bound is sharp, which generalizes the results due to Bondy (1980) for k=2 and Lu et al. (2005) for k=3.

Original language	English
Article number	112224
Journal	Discrete Mathematics
Volume	344
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2020.112224
Publication status	Published - Mar 2021

Keywords

Degree sums
Dominating cycle
Longest cycle

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

More information

10.1016/j.disc.2020.112224

Cite this

@article{26cf663d92e74c6fb3f878354fac3c99,

title = "Degree sums and dominating cycles",

abstract = "A cycle C of a graph G is dominating if any vertex of V(G)∖V(C) has at least one neighbor on C and V(G)∖V(C) is an independent set. Let G be a k-connected graph of order n≥3 with k≥2. In this paper, we show that every longest cycle of G is dominating if the degree sums is more than (k+1)(n+1)∕3 for any k+1 pairwise nonadjacent vertices, and the lower bound is sharp, which generalizes the results due to Bondy (1980) for k=2 and Lu et al. (2005) for k=3.",

keywords = "Degree sums, Dominating cycle, Longest cycle",

author = "Yueyu Wu and Yaojun Chen and Cheng, {T. C.Edwin}",

note = "Funding Information: This research was supported by NSFC, PR China under Grant Nos. 11671198 , 11871270 and 11931006 . Publisher Copyright: {\textcopyright} 2020 Elsevier B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2021",

month = mar,

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

language = "English",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Degree sums and dominating cycles

AU - Wu, Yueyu

AU - Chen, Yaojun

AU - Cheng, T. C.Edwin

N1 - Funding Information: This research was supported by NSFC, PR China under Grant Nos. 11671198 , 11871270 and 11931006 . Publisher Copyright: © 2020 Elsevier B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2021/3

Y1 - 2021/3

N2 - A cycle C of a graph G is dominating if any vertex of V(G)∖V(C) has at least one neighbor on C and V(G)∖V(C) is an independent set. Let G be a k-connected graph of order n≥3 with k≥2. In this paper, we show that every longest cycle of G is dominating if the degree sums is more than (k+1)(n+1)∕3 for any k+1 pairwise nonadjacent vertices, and the lower bound is sharp, which generalizes the results due to Bondy (1980) for k=2 and Lu et al. (2005) for k=3.

AB - A cycle C of a graph G is dominating if any vertex of V(G)∖V(C) has at least one neighbor on C and V(G)∖V(C) is an independent set. Let G be a k-connected graph of order n≥3 with k≥2. In this paper, we show that every longest cycle of G is dominating if the degree sums is more than (k+1)(n+1)∕3 for any k+1 pairwise nonadjacent vertices, and the lower bound is sharp, which generalizes the results due to Bondy (1980) for k=2 and Lu et al. (2005) for k=3.

KW - Degree sums

KW - Dominating cycle

KW - Longest cycle

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

U2 - 10.1016/j.disc.2020.112224

DO - 10.1016/j.disc.2020.112224

M3 - Journal article

AN - SCOPUS:85096374658

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

M1 - 112224

ER -

Degree sums and dominating cycles

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this