On the structure of extremal graphs of high girth
Lists
Only you see this
Abstract
Let n ≥ 3 be a positive integer, and let G be a simple graph of order v 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) v ≥ 8 and n = 5, or (ii) when v is large compared to n: v ≥ , where a = n - 3 - , n ≥ 12. On the other hand we prove that the answer to the question is negative for v = 2n + 2 ≥ 26. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 147–153, 1997
BibTeX
@article{lazebnik1997structure,
author = {Felix Lazebnik and Ping Wang},
title = {{On the structure of extremal graphs of high girth}},
journal = {Journal of Graph Theory},
year = {1997},
doi = {10.1002/(sici)1097-0118(199711)26:3<147::aid-jgt5>3.3.co;2-t},
}Loading related content...