On the structure of extremal graphs of high girth

Felix Lazebnik, Ping WangJournal of Graph Theory 1997 · DOI

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...

Figure