主題
Search

交集數

交集數 omega(G)，也稱為邊團覆蓋數、團邊覆蓋數、R-內容，或（容易混淆的）團覆蓋數，對於給定的圖 G，是指覆蓋 G 的所有邊所需的最小團的數量（即，其邊形成 G 的邊覆蓋）。根據此定義，只需要考慮極大團。

連通圖 G，具有頂點數 n 和邊數 m 滿足

omega(G)<=min(m,|_1/4n^2_|)
(1)

(Harary 1994, pp. 19-20)。

給出簡單無標號圖的三角形，其交集數為 k=0, 1, ..., |_n^2/4_|，對於 n=1, 2, ..., 由下式給出

1 1,1 1,2,1 1,3,4,2,1 1,4,9,10,7,2,1 1,5,17,36,46,30,14,4,2,1 1,6,28,97,219,281,226,116,45,18,5,1,1
(2)

(OEIS A355754)，而連通簡單無標號圖的相應三角形為

1 0,1 0,1,1 0,1,2,2,1 0,1,4,7,6,2,1 0,1,6,22,36,27,13,4,2,1 0,1,9,53,161,242,209,111,43,17,5,1,1
(3)

(OEIS A355755)。

對於具有 n>3 個頂點和 m 條邊的圖，omega(G)=m 當且僅當 G 是無三角形圖時成立 (Harary 1994, p. 19)。

Harary（1994，問題 2.26，p. 25）提出了尋找完全圖 K_n 的交集數的問題。雖然 Choudamand 和 Parthasarathy (1975)、Thomas (2004, p. 28) 以及 Jinnah 和 Mathew (2017) 似乎給出

omega(K_n)=[1+log_2n],
(4)

圖 K_n 是其自身的邊覆蓋這一事實要求對於 n>1，omega(K_n)=1。

另請參閱

團覆蓋數, 邊覆蓋, Erdős 序列, 圖的交集

使用 探索

參考文獻

Choudamand, S. A. 和 Parthasarathy, K. R. "關於一些圖的交集數。" Proc. Indian Nat. Sci. Acad. 41, Part A, No. 3, 307-317, 1975.Erdős, P.; Goodman, A. W.; 和 Póa, L. "用集合交集表示圖。" Canad. J. Math. 18, 106-112, 1966.Gross, J. T. 和 Yellen, J. 圖論及其應用，第二版。 Boca Raton, FL: CRC Press, p. 440, 2006.Harary, F. 圖論。 Reading, MA: Addison-Wesley, pp. 19-20, 1994.Harary, F. 和 Palmer, E. M. 圖形計數。 New York: Academic Press, p. 225, 1973.Harary, F. 和 Palmer, E. M. "圖計數問題綜述。" In 組合理論綜述 (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.Jinnah, M. I. 和 Mathew, S. C. "一些極大共軛圖的交集數。" Palestine J. Math. 6, 458-464, 2017.Roberts, F. S. "團的邊覆蓋的應用。" Disc. Appl. Math. 10, 93-109, 1985.Sloane, N. J. A. 序列 A355754 和 A355755 在 "整數序列線上百科全書" 中。Thomas, C. "代數圖論中的一些問題研究--由環產生的圖。" Ph. D. thesis. Thiruvananthapuram, India: University of Kerala, March 2004.

在 中引用

交集數

請引用為

Weisstein, Eric W. "交集數。" 來自 Web 資源。 https://mathworld.tw/IntersectionNumber.html

主題分類