菜单图标 主题
Search

上界无关数


图的上界无关数 IR(G) 是图 G 中顶点的一个 无关集 的最大尺寸。因此,它等于一个 最大无关集 以及一个 极大无关集 的尺寸,因为每个 最大无关集 也是极大的。上界无关数也等于一个 无关多项式 中最大的指数。

(下界)无关数 可以类似地定义为图 G 中顶点的一个 极大无关集 的最小尺寸(Burger 等人,1997;Mynhardt 和 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 等人,1997)。


另请参阅

无关数, 无关多项式, 无关集

使用 探索

参考文献

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "皇后图中的支配与无关性。" Disc. Math. 163, 47-66, 1997.Cockayne, E. J. and Mynhardt, C. M. "图的上界和下界支配数、独立数和无关数序列。" Disc. Math. 122, 89-102, 1993).Hedetniemi, S. T. and Laskar, R. C. "图的支配集参考书目以及支配参数的一些基本定义。" Disc. Math. 86, 257-277, 1990.Mynhardt, C. M. and Roux, A. "无关图。" 2020 年 4 月 14 日。 https://arxiv.org/abs/1812.03382.

请引用本文献为

Weisstein, Eric W. "上界无关数。" 来自 MathWorld—— 资源。 https://mathworld.net.cn/UpperIrredundanceNumber.html

主题分类