Extremal Graph
المؤلف:
Goodman, A. W
المصدر:
"On Sets of Acquaintances and Strangers at Any Party." Amer. Math. Monthly 66
الجزء والصفحة:
...
27-3-2022
1940
Extremal Graph
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,
![N(n)=<span style=]() {1/3m(m-1)(m-2) for n=2m; 1/32m(m-1)(4m+1) for n=4m+1; 1/32m(m+1)(4m-1) for n=4m+3. " src="https://mathworld.wolfram.com/images/equations/ExtremalGraph/NumberedEquation1.svg" style="height:93px; width:298px" /> |
(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).
REFERENCES
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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
