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:

Cycles through specified vertices in triangle-free graphs.

Paulusma, Daniel and Yoshimito, K. (2007) 'Cycles through specified vertices in triangle-free graphs.', Discussiones mathematicae graph theory., 27 (1). pp. 179-191.


Let G be a triangle-free graph with δ(G) ≥ 2 and σ4(G) ≥ |V(G)|+2. Let S ⊂ V(G) consist of less than σ4/4+ 1 vertices. We prove the following. If all vertices of S have degree at least three, then there exists a cycle C containing S. Both the upper bound on |S| and the lower bound on σ4 are best possible.

Item Type:Article
Keywords:Cycle, Path, Triangle-free graph.
Full text:PDF - Published Version (227Kb)
Publisher Web site:
Record Created:06 Oct 2010 15:20
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