TOPICS
Search

Haemers Number


The Haemers number of an n-vertex graph G, denoted H(G), H(G) (Alipour abd Gohari 2023), or R(G) (Haemers 1978), is an integer defined as the minimum rank over all n×n matrices B over some field such that b_(ii)!=0 and b_(ij)=0 if vertices i and j are not adjacent in a given graph G. (Note that the critical word "not" was inadvertently omitted in the original Haemers (1978) paper.)

The Haemers number provodes upper bound on the Shannon capacity of G which is sometimes better than the Lovász number.

The Haemers number satisfies

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

(Haemers 1978), where chi is the chromatic number and G^_ denotes the graph complement of G.


See also

Lovász Number, Shannon Capacity

Explore with Wolfram|Alpha

References

Alipour, S. and Gohari, A. "Relative Fractional Independence Number and Its Applications." 17 Jul 2023. https://arxiv.org/abs/2307.06155.Haemers, W. H. "An Upper Bound for the Shannon Capacity of a Graph." Colloq. Math. Soc. János Bolyai 25, 267-272, 1978.Taziki, M. "Relative Fractional Packing Number and Its Properties." 28 Nov 2023. https://arxiv.org/abs/2311.16390.

Cite this as:

Weisstein, Eric W. "Haemers Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HaemersNumber.html