選單圖示 主題
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. "上界無關數。" 來自 —— 資源。 https://mathworld.tw/UpperIrredundanceNumber.html

主題分類