Name
Abstract | ||
|---|---|---|
Bondy and Vince proved that every graph with minimum degree at least three contains two cycles whose lengths differ by one or two, which answers a question raised by Erdös. By a different approach, we show in this paper that if G is a graph with minimum degree δ(G) ≥ 3k for any positive integer k, then G contains k+1 cycles C0, C1, ... Ck such that k+1 E(C0)| E(C1)| E(Ck)|, |E(Ci)|- |E(Ci-1)|= 2, i ≤ i ≤ k - 1, and 1 ≤ |E(Ck)|-|E(Ck-1)| ≤ 2, and furthermore, if δ(G) ≥ 3k + 1, then |E(Ck)|-|E(Ck-1)|= 2. To settle a problem proposed by Bondy and Vince, we obtain that if G is a nonbipartite 3-connected graph with minimum degree at least 3k for any positive integer k, then G contains 2k cycles of consecutive lengths m, m+1, ..., m+2k-1 for some integer m ≥ k+2. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1006/jctb.2001.2071 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
3-connected graph,cycles c0,cycle length,different approach,consecutive lengths m,minimum degree,integer m,positive integer k,connected graph | Integer,Graph,Discrete mathematics,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
84 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
7 | 0.79 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 412 | 65.22 |