Skip to main content

Research Repository

Advanced Search

Cycles through specified vertices in triangle-free graphs

Paulusma, D.; Yoshimito, K.

Cycles through specified vertices in triangle-free graphs Thumbnail


Authors

K. Yoshimito



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.

Citation

Paulusma, D., & Yoshimito, K. (2007). Cycles through specified vertices in triangle-free graphs. Discussiones Mathematicae. Graph Theory, 27(1), 179-191. https://doi.org/10.7151/dmgt.1354

Journal Article Type Article
Publication Date Mar 1, 2007
Deposit Date Oct 6, 2010
Publicly Available Date Oct 8, 2010
Journal Discussiones mathematicae. Graph theory.
Print ISSN 1234-3099
Electronic ISSN 2083-5892
Publisher De Gruyter Open
Peer Reviewed Peer Reviewed
Volume 27
Issue 1
Pages 179-191
DOI https://doi.org/10.7151/dmgt.1354
Keywords Cycle, Path, Triangle-free graph.
Public URL https://durham-repository.worktribe.com/output/1538874

Files





You might also like



Downloadable Citations