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

Paulusma, D.; Yoshimoto, K.

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: Oct 7, 2010
• Journal: Discrete mathematics.
• Print ISSN: 0012-365X
• Electronic ISSN: 2578-9252
• 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