Cycles through specified vertices in triangle-free graphs

Paulusma, D.; Yoshimito, K.

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