Skip to main content

Research Repository

Advanced Search

Relative length of longest paths and longest cycles in triangle-free graphs

Paulusma, D.; Yoshimoto, K.

Relative length of longest paths and longest cycles in triangle-free graphs Thumbnail


Authors

K. Yoshimoto



Abstract

In this paper, we study triangle-free graphs. Let G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ4(G)|V(G)|+2. We first show that either for any path P in G there exists a cycle C such that |VPVC|1, or G is isomorphic to exactly one exception. Using this result, we show that for any set S of at most δ vertices in G there is a cycle C such that SVC.

Citation

Paulusma, D., & Yoshimoto, K. (2008). Relative length of longest paths and longest cycles in triangle-free graphs. Discrete Mathematics, 308(7), 1222-1229. https://doi.org/10.1016/j.disc.2007.03.070

Journal Article Type Article
Publication Date Apr 1, 2008
Deposit Date Oct 6, 2010
Publicly Available Date Mar 28, 2024
Journal Discrete mathematics.
Print ISSN 0012-365X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 308
Issue 7
Pages 1222-1229
DOI https://doi.org/10.1016/j.disc.2007.03.070
Keywords Triangle-free graph, Cycle, Ore-condition, Relative length.
Public URL https://durham-repository.worktribe.com/output/1515648

Files

Accepted Journal Article (210 Kb)
PDF

Copyright Statement
NOTICE: this is the author's version of a work that was accepted for publication in Discrete mathematics.





You might also like



Downloadable Citations