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 | Mar 28, 2024 |
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
An algorithmic framework for locally constrained homomorphisms
(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
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