Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


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.

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.

Item Type:Article
Keywords:Triangle-free graph, Cycle, Ore-condition, Relative length.
Full text:PDF - Accepted Version (205Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.disc.2007.03.070
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in Discrete mathematics.
Record Created:06 Oct 2010 14:50
Last Modified:03 Apr 2013 13:19

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library