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:(VoR) Version of Record
Download PDF
(227Kb)
Status:Peer-reviewed
Publisher Web site:http://lord.uz.zgora.pl:7777/bib/bibwww.bjournal?nIdCzasopisma=402
Date accepted:No date available
Date deposited:08 October 2010
Date of first online publication:March 2007
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar