Girth greater than 4

From Combinatorics Wiki

Revision as of 14:39, 3 January 2019 by Grahame (talk | contribs) (1 revision imported)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

Let G be an extremal graph of order n. Then

  1. the diameter of G is at most 3;
  2. if d(x)=δ(G)=1, then the graph G-{x} has diameter at most 2.

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

Known values and constructive lower bounds for ex(n;4)
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 94 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 270 275 280 285 291 296 301
80 306 311 317 323 329 334 340 346 352 357
90 363 368 374 379 385 391 398 404 410 416
100 422 428 434 440 446 452 458 464 470 476
110 483 489 495 501 508 514 520 526 532 538
120 544 551 558 565 571 578 584 590 596 603
130 610 617 623 630 637 644 651 658 665 672
140 679 686 693 700 707 714 721 728 735 742
150 749 756 763 770 777 784 791 798 805 812
160 819 826 834 841 849 856 863 871 878 886
170 893 901 909 917 925 933 941 948 956 963
180 971 979 986 994 1001 1009 1017 1025 1033 1041
190 1049 1057 1065 1073 1081 1089 1097 1105 1113 1121
200 1129

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

Color References
* 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>.