Ex(n;4)

From Combinatorics Wiki

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 n3/2.

Garnick et al. demonstrated that extremal graphs include:

  • Stars K1,n-1 and Paths Pn for n  ≤  4,
  • Moore graphs:
    • EX(5;4)={C5} 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.
  • C6 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. exl(240;4)=1560, exl(288;4)=2016, exl(312;4)=2340,exl(336;4)=2688, exl(448;4)=3808, exl(480;4)=4320,exl(512;4)=4864 and exl(576;4)=5760.

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

  • exl(2q2+q;4)=q2(q+1)+(q+1)ex(q;4) where q>1 is a prime power.
  • exl(2q2+q-h;4)=q2(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 />

Retrieved from ‘http://combinatoricswiki.org/index.php?title=Ex(n;4)&oldid=225’