A Convex Quadratic Characterization of the Lovász Theta Number
A Convex Quadratic Characterization of the Lovász Theta Number
复制标题
DOI：
10.1137/s0895480104429181
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
C. Luz;A. Schrijver
中科院分区：
文献类型：
--
作者：
C. Luz;A. Schrijver
在以往的工作中，引入了基于凸二次规划的图G的稳定性数$\alpha(G)$的上界，并建立了它的几个性质。本研究的目的是在理论上将这个界（通常用$\upsilon(G)$表示）与著名的Lovasz $\vartheta(G)$数字联系起来。首先，提出了一组新的$\alpha(G)$上的凸二次界，对$\upsilon(G)$界进行了推广和改进。然后证明$\vartheta(G)$不会比属于这组新界的任何界差。本笔记的主要结果表明，其中一个新边界等于$\vartheta(G)$，这一事实导致了洛瓦兹数的新表征。
In previous works an upper bound on the stability number $\alpha(G)$ of a graph G based on convex quadratic programming was introduced and several of its properties were established. The aim for this investigation is to relate theoretically this bound (usually represented by $\upsilon(G)$) with the well-known Lovasz $\vartheta(G)$ number. First, a new set of convex quadratic bounds on $\alpha(G)$ that generalize and improve the bound $\upsilon(G)$ is proposed. Then it is proved that $\vartheta(G)$ is never worse than any bound belonging to this set of new bounds. The main result of this note states that one of these new bounds equals $\vartheta(G)$, a fact that leads to a new characterization of the Lovasz theta number.