主题
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 容量

使用 Wolfram|Alpha 探索

参考文献

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 数。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/HaemersNumber.html