Abstract | ||
---|---|---|
Let n equal to or greater than 3 be a positive integer, and let G be a simple graph of order upsilon containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present several results where this question is answered affirmatively. For example, this is always the case for (i) upsilon equal to or greater than 8 and n = 5, or (ii) when upsilon is large compared to n: upsilon equal to or greater than 2(a2+a+1)n(a) where a = n - 3 - [n-2 /4], n equal to or greater than 12. On the other hand we prove that the answer to the question is negative for upsilon = 2n + 2 equal to or greater than 26. (C) 1997 John Wiley & Sons, Inc. |
Year | DOI | Venue |
---|---|---|
1997 | 3.0.CO;2-R" target="_self" class="small-link-text"10.1002/(SICI)1097-0118(199711)26:33.0.CO;2-R | Journal of Graph Theory |
Keywords | Field | DocType |
graph theory | Graph theory,Integer,Graph,Odd graph,Discrete mathematics,Combinatorics,Line graph,Symmetric graph,Windmill graph,Triangle-free graph,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 3 | 0364-9024 |
Citations | PageRank | References |
11 | 1.27 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Felix Lazebnik | 1 | 353 | 49.26 |
Ping Wang | 2 | 128 | 21.50 |