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:

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:(VoR) Version of Record
Download PDF
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
Look up in GoogleScholar | Find in a UK Library