Ex(n;4)

ex(n;4)

P.Erdös <ref>P. Erdös, Some recent progress on the extremal problems in graph theory, Congr. Numer. 14 (1975) 3--14</ref> conjectured that ex(n;4)=(1/2 + o(1))^3/2 n^3/2.

Garnick et al. demonstrated that extremal graphs include:

• Stars K_1,n-1 and Paths P_n for n  ≤  4,
• Moore graphs:
  • EX(5;4)={C₅} the cycle;
  • ex(10;4)= 15 is attained by the Petersen graph ;
  • ex(50;4)=175 is attained by the Hoffman-Singleton graph;
  • ex(3250;4) is attained by the Moore graph with girth 5 and degree 57 if it exists.
• C₆ is an element of EX(6;4).
• polarity graphs.

Large graphs, constructed by researches interested in The Cage Problem, provide good constructive lower bounds for the extremal number. These graphs are listed in the table when the number of vertices is less than 204. The higher order graphs produce the following lower bounds. ex_l(240;4)=1560, ex_l(288;4)=2016, ex_l(312;4)=2340,ex_l(336;4)=2688, ex_l(448;4)=3808, ex_l(480;4)=4320,ex_l(512;4)=4864 and ex_l(576;4)=5760.

Abajo, Balbuena and Di ́anez give the following constructive lower bounds for the extremal number:

• ex_l(2q²+q;4)=q²(q+1)+(q+1)ex(q;4) where q>1 is a prime power.
• ex_l(2q²+q-h;4)=q²(q+1)+(q+1)ex(q;4)-hq+e where q=8,9,11, e=-h for h=1,2 and e=-2 for h=3,...,q+1.

The following table lists the known values and constructive lower bounds for ex(n;4) for n < 204. If the value is known then it is shown in bold text.

Known values and constructive lower bounds for ex(n;4) for n < 204.

n	0	1	2	3	4	5	6	7	8	9
0	0	0	1	2	3	5	6	8	10	12
10	15	16	18	21	23	26	28	31	34	38
20	41	44	47	50	54	57	61	65	68	72
30	76	80	85	87	90	95	99	104	109	114
40	120	124	129	134	139	144	150	156	162	168
50	175	176	178	181	185	188	192	195	199	203
60	207	212	216	221	226	231	235	240	245	250
70	255	260	265	271	278	285	291	298	305	312
80	320	322	327	334	341	348	355	362	369	376
90	384	392	399	407	415	423	432	436	438	440
100	443	445	447	450	452	458	465	472	480	488
110	496	504	512	520	528	536	544	552	560	568
120	576	585	593	602	611	620	630	634	638	641
130	644	647	650	653	657	666	674	683	692	700
140	709	717	726	735	744	753	762	771	780	789
150	798	808	817	827	837	847	858	862	865	868
160	871	873	875	878	880	883	886	892	901	910
170	920	930	932	935	938	941	949	958	968	977
180	986	995	1004	1013	1022	1032	1042	1052	1062	1072
190	1082	1092	1102	1112	1122	1132	1142	1152	1163	1173
200	1184	1195	1206	1218	1223	1227	1231	1236	1240	1245

The following table is the key to the colors in the table presented above:

Color	References
*	Abajo, Balbuena and Di ́anez <ref>E. Abajo, C. Balbuena, A. Di ́anez, New families of graphs without short cycles and large size, Discrete Applied Mathematics 158 (2010), 1127–-1135</ref>
*	Exoo and Jajcay <ref>G. Exoo and R. Jajcay (2008), "Dynamic cage survey", The Electronic Journal of Combinatorics, Dynamic survey DS16 PDF version</ref>
*	Garnick, Kwong and Lazebnik<ref>D. K. Garnick and Y. H. H. Kwong, F. Lazebnik, Extremal graphs without three-cycles or four-cycles, J. Graph Theory, 17 (1993), 633--645</ref>.
*	Garnick and Nieuwejaar<ref>D. K. Garnick and N.A. Nieuwejaar, Non-isomorphic extremal graphs without three-cycles or four-cycles, JCMCC, 12 (1992), 33--56</ref>.
*	Marshall <ref>K Marshall, Interpolated lower bounds due to known large graphs.</ref>.

References

<references />