TY - JOUR

T1 - Circumference of a graph and its distance dominating longest cycles

AU - Fang, Yibin

AU - Xiong, Liming

N1 - Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2021/2

Y1 - 2021/2

N2 - In this note, we prove the following: Let G be a k-connected graph (k≥2) with circumference c(G) and m a non-negative integer. Then • [(1)] Either c(G)≥(2m+2)k, or dG(v,C)≤m for any longest cycle C and any vertex v of G. • [(2)] Either c(G)≥(2m+3)k, or dG(e,C)≤m for any longest cycle C and any edge e of G. When m=0, C in (1) and (2) are well-known Hamiltonian cycle and dominating longest cycle, respectively. Moreover, we give graphs to show that the bounds on c(G) are all sharp, even for those graphs that are triangle-free with only possible exception m=0 in (2). (1) is also best possible for those graphs that are bipartite.

AB - In this note, we prove the following: Let G be a k-connected graph (k≥2) with circumference c(G) and m a non-negative integer. Then • [(1)] Either c(G)≥(2m+2)k, or dG(v,C)≤m for any longest cycle C and any vertex v of G. • [(2)] Either c(G)≥(2m+3)k, or dG(e,C)≤m for any longest cycle C and any edge e of G. When m=0, C in (1) and (2) are well-known Hamiltonian cycle and dominating longest cycle, respectively. Moreover, we give graphs to show that the bounds on c(G) are all sharp, even for those graphs that are triangle-free with only possible exception m=0 in (2). (1) is also best possible for those graphs that are bipartite.

KW - Circumference

KW - Connectivity

KW - Distance dominating cycle

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

U2 - 10.1016/j.disc.2020.112196

DO - 10.1016/j.disc.2020.112196

M3 - Article

AN - SCOPUS:85094186526

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

M1 - 112196

ER -