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.
|Keywords:||Triangle-free graph, Cycle, Ore-condition, Relative length.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (205Kb)
|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:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|