Cookies

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.

Abstract

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)
Status:Peer-reviewed
Publisher Web site:http://lord.uz.zgora.pl:7777/bib/bibwww.bjournal?nIdCzasopisma=402
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