主題
Search

Haemers 數

一個 n-頂點圖 G 的 Haemers 數，記作 H(G), H(G) (Alipour abd Gohari 2023), 或 R(G) (Haemers 1978)，是一個整數，定義為在某個域上所有 n×n 矩陣 B 的最小秩，使得 b_(ii)!=0 且 b_(ij)=0 如果頂點 i 和 j 在給定圖 G 中不相鄰。（注意，原始 Haemers (1978) 論文中不小心遺漏了關鍵的詞語“不”。）

Haemers 數為圖 G 的 Shannon 容量提供了上限，有時比 Lovász 數更好。

Haemers 數滿足

R(G)<=chi(G^_)

(Haemers 1978), 其中 chi 是色數，而 G^_ 表示圖 G 的補圖。

另請參閱

Lovász 數, Shannon 容量

使用 探索

參考文獻

Alipour, S. 和 Gohari, A. "相對分數獨立數及其應用。" 2023 年 7 月 17 日。 https://arxiv.org/abs/2307.06155.Haemers, W. H. "圖的 Shannon 容量的上限。" Colloq. Math. Soc. János Bolyai 25, 267-272, 1978.Taziki, M. "相對分數填充數及其性質。" 2023 年 11 月 28 日。 https://arxiv.org/abs/2311.16390.

請引用為

Weisstein, Eric W. "Haemers 數。" 來自 —— 資源。 https://mathworld.tw/HaemersNumber.html