主题
Search

冗余数

图 G 的（下）冗余数 ir(G) 是 极大冗余集 在 G 中的最小尺寸。

上冗余数 定义为 冗余集 在 G 中顶点的最大尺寸（Burger et al. 1997, Mynhardt and Roux 2020）。换句话说，它是 最大冗余集 的尺寸，这与 极大冗余集 的最大尺寸相同，因为所有最大冗余集也是极大的。

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

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

(Burger et al. 1997)。

参见

冗余多项式, 冗余集, 上冗余数

使用 Wolfram|Alpha 探索

参考文献

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).Hedetniemi, S. T. and Laskar, R. C. "A. Bibliography on Dominating Sets in Graphs and Some Basic Definitions of Domination Parameters." Disc. Math. 86, 257-277, 1990.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.

引用为

Weisstein, Eric W. "Irredundance Number." 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/IrredundanceNumber.html

主题分类