We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Paulusma, Daniel and Yoshimoto, K. (2008) 'Relative length of longest paths and longest cycles in triangle-free graphs.', Discrete mathematics., 308 (7). pp. 1222-1229.


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.

Item Type:Article
Keywords:Triangle-free graph, Cycle, Ore-condition, Relative length.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in Discrete mathematics.
Date accepted:No date available
Date deposited:07 October 2010
Date of first online publication:April 2008
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar