主题
Search

极图

一般来说，极图是不包含给定图 G 作为子图的具有最大阶数 n 的图 (Skiena 1990, p. 143)。Turán 研究了不包含完全图 K_p 作为子图的极图。

一种备受研究的极图类型是对完全图 K_n 的 n 个节点的双色着色，其中恰好包含数量 N=(R+B)_(min) 的单色强制三角形，且不再多（即，最少 R+B，其中 R 和 B 是红色和蓝色三角形的数量）。Goodman (1959) 表明，对于这种类型的极图，

N(n)={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.
(1)

这有时被称为 Goodman 公式。Schwenk (1972) 将其改写为形式

N(n)=(n; 3)-|_1/2n|_1/4(n-1)^2_|_|,
(2)

有时被称为 Schwenk 公式，其中 |_x_| 是向下取整函数。N(n) 对于 n=1, 2, ... 的前几个值是 0, 0, 0, 0, 0, 2, 4, 8, 12, 20, 28, 40, 52, 70, 88, ... (OEIS A014557)。

另请参阅

双色图, 蓝色空图, 极图理论, Goodman 公式, 单色强制三角形, Schwenk 公式, Turán 图

使用 Wolfram|Alpha 探索

参考资料

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."

在 Wolfram|Alpha 上引用

极图

引用为

Weisstein, Eric W. "极图。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/ExtremalGraph.html

主题分类