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.|
|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|