Read More
Date: 17-3-2022
1657
Date: 13-3-2022
1289
Date: 3-4-2022
1856
|
In general, an extremal graph is the largest graph of order which does not contain a given graph as a subgraph (Skiena 1990, p. 143). Turán studied extremal graphs that do not contain a complete graph as a subgraph.
One much-studied type of extremal graph is a two-coloring of a complete graph of nodes which contains exactly the number of monochromatic forced triangles and no more (i.e., a minimum of where and are the numbers of red and blue triangles). Goodman (1959) showed that for an extremal graph of this type,
(1) |
This is sometimes known as Goodman's formula. Schwenk (1972) rewrote it in the form
(2) |
sometimes known as Schwenk's formula, where is the floor function. The first few values of for , 2, ... are 0, 0, 0, 0, 0, 2, 4, 8, 12, 20, 28, 40, 52, 70, 88, ... (OEIS A014557).
Goodman, A. W. "On Sets of Acquaintances and Strangers at Any Party." Amer. Math. Monthly 66, 778-783, 1959.
Schwenk, A. J. "Acquaintance Party Problem." Amer. Math. Monthly 79, 1113-1117, 1972.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 143, 1990.
Sloane, N. J. A. Sequence A014557 in "The On-Line Encyclopedia of Integer Sequences."
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|