Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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.
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 |
Published Journal Article
(231 Kb)
PDF
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
The Complexity of Matching Games: A Survey
(2023)
Journal Article
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
Journal Article
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search