主题
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.net.cn/IntersectionNumber.html

主题分类