Extremal C t-free graphs

This topic is currently being edited. New and more complete information will be added soon. Thank-you for your patience.

Introduction

A graph G is an extremal C_t-free graph if G has maximal size and girth g at least t+1. The set of extremal C_t-free graphs is denoted by EX(n;t)=EX(n;{C ₃,C₄,...,C_t}) and the size of the graph is the extremal number ex(n;t)=ex(n;{C ₃,C₄,...,C_t}).

Known Results

This section includes links to tables that present a summary of current known values of ex(n;t) for ex(n;4), ex(n;5), ex(n;6), ex(n;7) and ex(n;8). Additionally, the table ex(n;t) lists some known values for ex(n;t) for n=1,2,...,50 and t=4,5,...,13.

If the exact value of ex(n;t) is known then the value is shown in bold text, where the exact value of ex(n;t) is not yet known constructive lower bounds are displayed in the table cells. When there are two values in the table cell these represent the current known upper and lower bounds of the extremal number. The background colour of the table cells indicates the source of these values. The key to the colours is in another table below the known values.

For for n  ≤  t, it is easy to show that the Stars K_1,n-1 and Paths P_n are extremal graphs and ex(n;t)=n-1. For t+1  ≤  n  ≤  [math]\lfloor 3t/2 \rfloor [/math] the Cycles C_n are extremal graphs and ex(n;t)=n. These values are included in the tables as folklore.

The problem of finding the extremal number ex(n;3) is solved by Mantel's theorem which states that the maximum size of a triangle free graph of order n is [math]\lfloor {{n^2}/4}\rfloor[/math]. The extremal graphs [math]EX(n;3)[/math] are the complete bipartite graphs [math]K_{{\lfloor n/2 \rfloor}{\lceil n/2 \rceil}}[/math].

References

<references />