主題
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, ...

另請參閱

博爾德猜想, 團圖, 團多項式, 分數團數, 獨立數, 極大團, 最大團

使用 探索

參考文獻

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

在 上被引用

團數

請引用為

Weisstein, Eric W. “團數。” 來自 Web 資源。 https://mathworld.tw/CliqueNumber.html

主題分類