Open AccessCycles through specified vertices in triangle-free graphs
Author(s) -
Daniël Paulusma,
Kiyoshi Yoshimoto
Publication year - 2007
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1354
Subject(s) - combinatorics , mathematics , upper and lower bounds , path graph , graph , bound graph , wheel graph , discrete mathematics , graph power , line graph , mathematical analysis
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom