Abstract
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.
Original language | English |
---|---|
Article number | 112196 |
Journal | Discrete Mathematics |
Volume | 344 |
Issue number | 2 |
DOIs | |
Publication status | Published - Feb 2021 |
Keywords
- Circumference
- Connectivity
- Distance dominating cycle
Fingerprint
Dive into the research topics of 'Circumference of a graph and its distance dominating longest cycles'. Together they form a unique fingerprint.Cite this
Fang, Y., & Xiong, L. (2021). Circumference of a graph and its distance dominating longest cycles. Discrete Mathematics, 344(2), Article 112196. https://doi.org/10.1016/j.disc.2020.112196