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
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
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 © 2024
Advanced Search