主题
Search

独立数

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

图的（上）顶点独立数，也称为 1-填充数、填充数或稳定性数 (Acín et al. 2016)，通常简称为“独立数”，是最大独立顶点集的基数，即最大独立顶点集（与最大极大独立顶点集的大小相同）的大小。独立数最常用的符号是 alpha(G)，但也可能写成 beta(G)（例如，Burger et al. 1997）或 beta_0(G)（例如，Bollobás 1981）。

图的独立数等于该图的独立多项式中的最大指数。

下独立数 i(G) 可以类似地定义为 G 中最小极大独立顶点集的大小 (Burger et al. 1997)。

下冗余数 ir(G)、下支配数 gamma(G)、下独立数 i(G)、上独立数 alpha(G)、上支配数 Gamma(G) 和 上冗余数 IR(G) 满足以下不等式链

ir(G)<=gamma(G)<=i(G)<=alpha(G)<=Gamma(G)<=IR(G)
(1)

(Burger et al. 1997)。

图 G 的独立数与其顶点数的比率称为 G 的独立比率 (Bollobás 1981)。

图 G 的独立数等于补图的团数，

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

对于 n>1 个顶点且顶点度为 k 和最小图特征值为 s 的连通正则图 G，

alpha<=(n(-s))/(k-s)
(3)

(A. E. Brouwer，私人通信，2012 年 12 月 17 日)。

对于r，图半径，

alpha>=r
(4)

(DeLa Vina 和 Waller 2002)。Lovasz (1979, p. 55) 表明，当 rho 是路径覆盖数时，

alpha>=rho,
(5)

仅对于完全图等式成立 (DeLa Vina 和 Waller 2002)。

Willis (2011) 给出了图的独立数的若干界限。

图 G 的匹配数 nu(G) 等于其线图 L(G) 的独立数 alpha(L(G))。

根据定义，

alpha(G)+tau(G)=|G|,
(6)

其中 tau(G) 是 G 的顶点覆盖数，n=|G| 是其顶点数 (West 2000)。

具有顶点集 V 和 边集 E 的图 G 的独立数可以定义为整数规划的结果

alpha(G)=max_(w_i+w_j<=1 for e_(ij) in E; w_i in {0,1})sum_(v in V)w_i
(7)

其中 w_i=w(v_i) 是第 i 个顶点上的权重。将此条件放宽为允许 w_i in [0,1] 得到分数独立数 alpha^*(G)。

许多命名图的预计算独立数可以在 Wolfram 语言中使用以下命令获得GraphData[graph,"IndependenceNumber"].

下面总结了某些图类的已知值。

图 Galpha(G)OEIS值
交错群图 AG_nA0000001, 1, 4, 20, 120, ...
n-Andrásfai 图 (n>=3)nA0000273, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
n-反棱柱图 (n>=3)|_2n/3_|A0045232, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, ...
n-阿波罗尼安网络3^(n-1)A0002441, 3, 9, 27, 81, 243, 729, 2187, ...
完全二部图 K_(n,n)nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
完全图 K_n1A0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
完全三部图 K_(n,n,n)nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
圈图 C_n (n>=3)|_n/2_|A0045261, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ...
空图 K^__nnA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
n-折叠立方体图 (n>=2)2^(n-2)-1/4(1-(-1)^n)(n-1; (n-1)/2)A0586221, 1, 4, 5, 16, 22, 64, 93, 256, ...
网格图 P_n square P_n[n^2/2]A0009821, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
网格图 P_n square P_n square P_n[n^3/2]A0364861, 4, 14, 32, 63, 108, 172, 256, 365, 500, ...
n-半立方体图A0058641, 1, 4, 5, 16, 22, 64, 93, 256, ...
n-汉诺塔图3^(n-1)A0002441, 3, 9, 27, 81, 243, 729, 2187, ...
超立方体图 Q_n2^(n-1)A0000791, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
n-Keller 图{4 for n=1; 5 for n=2; 2^n otherwiseA2589354, 5, 8, 16, 32, 64, 128, 256, 512, ...
(n,n)-国王图 (n>=2)|_(n+1)/2_|^2A0087941, 4, 4, 9, 9, 16, 16, 25, 25
(n,n)-骑士图 (n>=2){4 for n=2; (1+(-1)^(n+1)+2n^2)/4 otherwiseA0309784, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
克内泽尔图 K(n,k)(n-1; k-1)
n-Mycielski 图{1 for n=1,2; 3·2^(n-3)-1 otherwiseA2665501, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ...
莫比乌斯梯子图 M_n (n>=3)2[n/2]-1A1096133, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, ...
奇图 O_n{1 for n=1; (2n-2; n-2) otherwiseA0000001, 1, 4, 15, 56, 210, 792, 3003, 11440, ...
n-平底锅图1+|_n/2_|A0000002, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ...
路径图 P_n[n/2]A0045261, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...
棱柱图 Y_n (n>=3)2|_n/2_|A0529282, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ...
n-谢尔宾斯基地毯图4, 32, 256, ...
n-谢尔宾斯基垫片图1, 3, 6, 15, 42, ...
星图 S_n{1 for n=1; n-1 otherwiseA0283101, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
三角形图 T_n (n>=2)|_n/2_|A0045261, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ...
n-网状图 (n>=3)1/4[6n+(-1)^n-1]/4A0327664, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, ...
轮图 W_n|_(n-1)/2_|A0045261, 2, 2, 3, 3, 4, 4, 5, 5, ...

另请参阅

团数, 分数独立数, 独立多项式, 独立比率, 独立集, 下独立数, 匹配数, 最大独立顶点集, 最小顶点覆盖, Shannon 容量, 顶点覆盖

使用 Wolfram|Alpha 探索

参考文献

Acín, A.; Duan, R.; Roberson, D. E.; Belén Sainz, A.; 和 Winter, A. "a New Property of the Lovász Number and Duality Relations Between Graph Parameters." 2016 年 2 月 5 日。 https://arxiv.org/abs/1505.01265.Bollobás, B. "The Independence Ratio of Regular Graphs." Proc. Amer. Math. Soc. 83, 433-436, 1981.Burger, A. P.; Cockayne, E. J.; 和 Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Cockayne, E. J. 和 Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).DeLa Vina, E. 和 Waller, B. "Independence, Radius and Path Coverings in Trees." Congr. Numer. 156, 155-169, 2002.Lovasz, L. Combinatorial Problems and Exercises. Academiai Kiado, 1979.Skiena, S. "Maximum Independent Set" §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.Sloane, N. J. A. 序列 A000012/M0003, A000027/M0472, A000079/M1129, A000244/M2807, A000982/M1348, A004523, A004526, A005864/M1111, A008794, A028310, A030978, A032766, A036486, A052928, A058622, A109613, A258935, 和 A266550 West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.Willis, W. "Bounds for the Independence Number of a Graph." 硕士论文。Richmond, VA: Virginia Commonwealth University, 2011.

在 Wolfram|Alpha 中被引用

独立数

请引用为

Weisstein, Eric W. "Independence Number." 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/IndependenceNumber.html

主题分类