
























A well known upper bound for the independence number $α(G)$ of a graph $G$, is that \[ α(G) \le n^0 + \min\{n^+ , n^-\}, \] where $(n^+, n^0, n^-)$ is the inertia of $G$. We prove that this bound is also an upper bound for the quantum independence number $α_q$(G), where $α_q(G) \ge α(G)$. We identify numerous graphs for which $α(G) = α_q(G)$ and demonstrate that there are graphs for which the above bound is not exact with any Hermitian weight matrix, for $α(G)$ and $α_q(G)$. This result complements results by the authors that many spectral lower bounds for the chromatic number are also lower bounds for the quantum chromatic number.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。