On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs

• المؤلفون الرئيسيون: Sotirov, R., Klerk, Etienne de., Newman, M. W., Pasechnik, Dmitrii V.
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2012
• الموضوعات: DRNTU::Science::Mathematics
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/94538; http://hdl.handle.net/10220/7516

We consider k-regular graphs with loops, and study the Lovász ϑ-numbers and Schrijver ϑ′-numbers of the graphs that result when the loop edges are removed. We show that the ϑ-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newma...