On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2012
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/94538 http://hdl.handle.net/10220/7516 |
| _version_ | 1826121220569956352 |
|---|---|
| author | Sotirov, R. Klerk, Etienne de. Newman, M. W. Pasechnik, Dmitrii V. |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Sotirov, R. Klerk, Etienne de. Newman, M. W. Pasechnik, Dmitrii V. |
| author_sort | Sotirov, R. |
| collection | NTU |
| description | 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. Newman. Eigenvalue bounds for independent sets, J. Combin. Theory B 98 (4) (2008) 721–734].
As an application we compute the ϑ and ϑ′ numbers of certain instances of Erdős–Rényi graphs. This computation exploits the graph symmetry using the methodology introduced in [E. de Klerk, D.V. Pasechnik and A. Schrijver, Reduction of symmetric semidefinite programs using the regular *-representation, Math. Program. B 109 (2–3) (2007) 613–624].
The computed values are strictly better than the Godsil–Newman eigenvalue bounds. |
| first_indexed | 2024-10-01T05:28:49Z |
| format | Journal Article |
| id | ntu-10356/94538 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:28:49Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | ntu-10356/945382023-02-28T19:39:30Z 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 DRNTU::Science::Mathematics 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. Newman. Eigenvalue bounds for independent sets, J. Combin. Theory B 98 (4) (2008) 721–734]. As an application we compute the ϑ and ϑ′ numbers of certain instances of Erdős–Rényi graphs. This computation exploits the graph symmetry using the methodology introduced in [E. de Klerk, D.V. Pasechnik and A. Schrijver, Reduction of symmetric semidefinite programs using the regular *-representation, Math. Program. B 109 (2–3) (2007) 613–624]. The computed values are strictly better than the Godsil–Newman eigenvalue bounds. Accepted version 2012-02-07T05:51:32Z 2019-12-06T18:57:39Z 2012-02-07T05:51:32Z 2019-12-06T18:57:39Z 2008 2008 Journal Article Klerk, E. D., Newman, M. W., Pasechnik, D. V. & Sotirov R. (2009). On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs. European Journal of Combinatorics, 30(4), 879–888 https://hdl.handle.net/10356/94538 http://hdl.handle.net/10220/7516 10.1016/j.ejc.2008.07.022 en European journal of combinatorics © 2008 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by European Journal of Combinatorics, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [DOI: http://dx.doi.org/10.1016/j.ejc.2008.07.022 ] 16 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics Sotirov, R. Klerk, Etienne de. Newman, M. W. Pasechnik, Dmitrii V. On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs |
| title | On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs |
| title_full | On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs |
| title_fullStr | On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs |
| title_full_unstemmed | On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs |
| title_short | On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs |
| title_sort | on the lovasz ϑ number of almost regular graphs with application to erdos renyi graphs |
| topic | DRNTU::Science::Mathematics |
| url | https://hdl.handle.net/10356/94538 http://hdl.handle.net/10220/7516 |
| work_keys_str_mv | AT sotirovr onthelovaszthnumberofalmostregulargraphswithapplicationtoerdosrenyigraphs AT klerketiennede onthelovaszthnumberofalmostregulargraphswithapplicationtoerdosrenyigraphs AT newmanmw onthelovaszthnumberofalmostregulargraphswithapplicationtoerdosrenyigraphs AT pasechnikdmitriiv onthelovaszthnumberofalmostregulargraphswithapplicationtoerdosrenyigraphs |