Premium
On the structure of extremal graphs of high girth
Author(s) -
Lazebnik Felix,
Wang Ping
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199711)26:3<147::aid-jgt5>3.0.co;2-r
Subject(s) - combinatorics , mathematics , graph , girth (graph theory) , integer (computer science) , extremal graph theory , discrete mathematics , order (exchange) , simple (philosophy) , line graph , voltage graph , computer science , programming language , philosophy , finance , epistemology , economics
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 ≥ $2^{a^{2}+a+1}n^{a}$ , where a = n ‐ 3 ‐ $\lfloor{n-2}\over{4}\rfloor$ , n ≥ 12. On the other hand we prove that the answer to the question is negative for v = 2 n + 2 ≥ 26. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 147–153, 1997