Grahame: 1 revision imported

2019-01-03T14:39:32Z

1 revision imported

CW>KimMarshall at 05:07, 30 March 2011

2011-03-30T05:07:56Z

New page

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

==Introduction==

A [http://en.wikipedia.org/wiki/Graph_%28mathematics%29 graph] ''G'' is an extremal ''Ct''-free graph if ''G'' has maximal size and [http://en.wikipedia.org/wiki/Girth_(graph_theory) girth] ''g'' at least ''t+1''. The set of extremal ''Ct''-free graphs is denoted by ''EX(n;t)=EX(n;{C 3,C4,...,Ct})'' and the size of the graph is the extremal number ''ex(n;t)=ex(n;{C 3,C4,...,Ct})''.

==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 [http://en.wikipedia.org/wiki/Star_(graph_theory) Stars] ''K1,n-1'' and [http://en.wikipedia.org/wiki/Path_(graph_theory) Paths] ''Pn'' are extremal graphs and ''ex(n;t)=n-1''. For ''t+1''  ≤  ''n''  ≤  <math>\lfloor 3t/2 \rfloor </math> the [http://en.wikipedia.org/wiki/Cycle_graph Cycles] ''Cn'' 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 [http://en.wikipedia.org/wiki/Triangle-free_graph triangle free graph] of order ''n'' is <math>\lfloor {{n^2}/4}\rfloor</math>. The extremal graphs <math>EX(n;3)</math> are the [http://en.wikipedia.org/wiki/Complete_bipartite_graph complete bipartite graphs] <math>K_{{\lfloor n/2 \rfloor}{\lceil n/2 \rceil}}</math>.

== References ==
<references />

← Older revision	Revision as of 14:39, 3 January 2019
(No difference)

Extremal C t-free graphs - Revision history

Grahame: 1 revision imported

CW>KimMarshall at 05:07, 30 March 2011