主题
Search

团数


G 的(上限)团数,记为 omega(G),是 最大团 中顶点的数量 G。等效地,它是最大 极大团的大小 G

图的团数 omega(G) 等于该图的团多项式中的最大指数。

下团数 omega_L(G) 可以类似地定义为图的最小极大团的大小。

对于任意

 omega(G)>=sum_(i=1)^n1/(n-d_i),
(1)

其中 d_ii顶点度

图的团数等于补图独立数

 omega(G)=alpha(G^_).
(2)

G色数 chi(G) 等于或大于其团数 omega(G),即,

 chi(G)>=omega(G).
(3)

下表列出了一些命名图的团数。

下表给出了对于小 k,具有团数 kn 节点图的数量 N_k(n)

kOEISN_k(n)
11, 1, 1, 1, 1, 1, 1, 1, ...
2A0524500, 1, 2, 6, 13, 37, 106, 409, 1896, ...
3A0524510, 0, 1, 3, 15, 82, 578, 6021, 101267, ...
4A0524520, 0, 0, 1, 4, 30, 301, 4985, 142276, ...
5A0773920, 0, 0, 0, 1, 5, 51, 842, 27107, ...
6A0773930, 0, 0, 0, 0, 1, 6, 80, 1995, ...
7A0773940, 0, 0, 0, 0, 0, 1, 7, 117, ...
80, 0, 0, 0, 0, 0, 0, 1, 8, ...

另请参阅

博尔德猜想, 团图, 团多项式, 分数团数, 独立数, 极大团, 最大团

使用 Wolfram|Alpha 探索

参考文献

Aigner, M. "Turán's Graph Theorem." Amer. Math. Monthly 102, 808-816, 1995.Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.Hastad, J. "Clique Is Hard to Approximate Within n^(1-epsilon)." Acta Math. 182, 105-142, 1999.Sloane, N. J. A. Sequences A052450, A052451, A052452, A077392, A077393, and A077394 in "The On-Line Encyclopedia of Integer Sequences."

在 Wolfram|Alpha 上被引用

团数

请引用为

Weisstein, Eric W. “团数。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CliqueNumber.html

主题分类