交集数 -- 来自 Wolfram MathWorld

交集数

交集数，也称为边团覆盖数、团边覆盖数、-内容，或（容易混淆的）团覆盖数，对于给定的图，是指覆盖的所有边所需的最小团的数量（即，其边形成的边覆盖）。根据此定义，只需要考虑极大团。

连通图，具有顶点数和边数满足

(1)

(Harary 1994, pp. 19-20)。

给出简单无标号图的三角形，其交集数为 , 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)。

对于具有个顶点和条边的图，当且仅当是无三角形图时成立 (Harary 1994, p. 19)。

Harary（1994，问题 2.26，p. 25）提出了寻找完全图的交集数的问题。虽然 Choudamand 和 Parthasarathy (1975)、Thomas (2004, p. 28) 以及 Jinnah 和 Mathew (2017) 似乎给出

(4)

图是其自身的边覆盖这一事实要求对于，。

另请参阅

团覆盖数, 边覆盖, Erdős 序列, 图的交集

使用 Wolfram|Alpha 探索

更多尝试

参考文献

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.

在 Wolfram|Alpha 中引用

交集数

请引用为

Weisstein, Eric W. "交集数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/IntersectionNumber.html