mirage

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

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

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

Show simple item record

dc.contributor.author Klerk, Etienne de.
dc.contributor.author Newman, M. W.
dc.contributor.author Pasechnik, Dmitrii V.
dc.contributor.author Sotirov, R.
dc.date.accessioned 2012-02-07T05:51:32Z
dc.date.available 2012-02-07T05:51:32Z
dc.date.copyright 2008
dc.date.issued 2012-02-07
dc.identifier.citation 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
dc.identifier.uri http://hdl.handle.net/10220/7516
dc.description.abstract 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.
dc.format.extent 16 p.
dc.language.iso en
dc.relation.ispartofseries European journal of combinatorics
dc.rights © 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 ]
dc.subject DRNTU::Science::Mathematics.
dc.title On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs.
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.doi http://dx.doi.org/10.1016/j.ejc.2008.07.022
dc.description.version Accepted version

Files in this item

Files Size Format View
4. On the Lovász #-number of almost (editing).pdf 458.3Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Statistics

Total views

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

Total downloads

All Bitstreams Views
4. On the Lovász #-number of almost (editing).pdf 77

Top country downloads

Country Code Views
United States of America 39
Singapore 12
China 9
Unknown Country 2
Japan 2

Top city downloads

city Views
Mountain View 31
Singapore 12
Beijing 2
Milan 1
Munich 1

Downloads / month

  2014-07 2014-08 2014-09 total
4. On the Lovász #-number of almost (editing).pdf 0 0 2 2