Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650744 | Discrete Mathematics | 2008 | 8 Pages |
Abstract
In this paper, we study triangle-free graphs. Let G=(V,E)G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ4(G)⩾|V(G)|+2σ4(G)⩾|V(G)|+2. We first show that either for any path PP in GG there exists a cycle CC such that |VP⧹VC|⩽1|VP⧹VC|⩽1, or GG is isomorphic to exactly one exception. Using this result, we show that for any set SS of at most δδ vertices in GG there is a cycle CC such that S⊆VCS⊆VC.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daniel Paulusma, Kiyoshi Yoshimoto,