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...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2012
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/94538 http://hdl.handle.net/10220/7516 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-94538 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.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 |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Science::Mathematics |
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 |
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. |
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. |
format |
Article |
author |
Sotirov, R. Klerk, Etienne de. Newman, M. W. Pasechnik, Dmitrii V. |
author_sort |
Sotirov, R. |
title |
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_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_sort |
on the lovász ϑ-number of almost regular graphs with application to erdős–rényi graphs |
publishDate |
2012 |
url |
https://hdl.handle.net/10356/94538 http://hdl.handle.net/10220/7516 |
_version_ |
1759855622949437440 |