Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Relative length of longest paths and longest cycles in triangle-free graphs
Paulusma, D.; Yoshimoto, K.
Authors
K. Yoshimoto
Abstract
In this paper, we study triangle-free graphs. Let G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ4(G)|V(G)|+2. We first show that either for any path P in G there exists a cycle C such that |VPVC|1, or G is isomorphic to exactly one exception. Using this result, we show that for any set S of at most δ vertices in G there is a cycle C such that SVC.
Citation
Paulusma, D., & Yoshimoto, K. (2008). Relative length of longest paths and longest cycles in triangle-free graphs. Discrete Mathematics, 308(7), 1222-1229. https://doi.org/10.1016/j.disc.2007.03.070
Journal Article Type | Article |
---|---|
Publication Date | Apr 1, 2008 |
Deposit Date | Oct 6, 2010 |
Publicly Available Date | Oct 7, 2010 |
Journal | Discrete mathematics. |
Print ISSN | 0012-365X |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 308 |
Issue | 7 |
Pages | 1222-1229 |
DOI | https://doi.org/10.1016/j.disc.2007.03.070 |
Keywords | Triangle-free graph, Cycle, Ore-condition, Relative length. |
Public URL | https://durham-repository.worktribe.com/output/1515648 |
Files
Accepted Journal Article
(210 Kb)
PDF
Copyright Statement
NOTICE: this is the author's version of a work that was accepted for publication in Discrete mathematics.
You might also like
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
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
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