Algebras, Graphs and Thetas

Marcel K. De Carli Silva; Gabriel Coutinho; Chris Godsil; David E. Roberson

doi:10.1016/j.entcs.2019.08.025

Algebras, Graphs and Thetas

Marcel K. De Carli Silva, Gabriel Coutinho, Chris Godsil, David E. Roberson

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Conference article › Research › peer-review

87 Downloads (Pure)

Abstract

We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations and 1-walk regular graphs. We further generalize it to a stronger inequality involving the Lovász theta number of such graph, and some theta variants, including characterizations of the equality.

Original language	English
Journal	Electronic Notes in Theoretical Computer Science
Volume	346
Pages (from-to)	275-283
ISSN	1571-0661
DOIs	https://doi.org/10.1016/j.entcs.2019.08.025
Publication status	Published - 1 Jan 2019
Event	10th Latin and American Algorithms, Graphs and Optimization Symposium, - Belo Horizonte, Brazil Duration: 2 Jun 2019 → 7 Jun 2019 Conference number: 10

Conference

Conference	10th Latin and American Algorithms, Graphs and Optimization Symposium,
Number	10
Country/Territory	Brazil
City	Belo Horizonte
Period	02/06/2019 → 07/06/2019

Keywords

Clique-coclique inequality
Coherent configuration
Lovász theta function
Matrix-algebra

Access to Document

10.1016/j.entcs.2019.08.025

FulltextFinal published version, 219 KBLicence: CC BY-NC-ND

OpenUrl availability

Full text

Cite this

@inproceedings{2fec3ac5295e47cda154a359a80f6504,

title = "Algebras, Graphs and Thetas",

abstract = "We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations and 1-walk regular graphs. We further generalize it to a stronger inequality involving the Lov{\'a}sz theta number of such graph, and some theta variants, including characterizations of the equality.",

keywords = "Clique-coclique inequality, Coherent configuration, Lov{\'a}sz theta function, Matrix-algebra",

author = "{De Carli Silva}, {Marcel K.} and Gabriel Coutinho and Chris Godsil and Roberson, {David E.}",

year = "2019",

month = jan,

day = "1",

doi = "10.1016/j.entcs.2019.08.025",

language = "English",

volume = "346",

pages = "275--283",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier",

note = "10th Latin and American Algorithms, Graphs and Optimization Symposium, , LAGOS 2019 ; Conference date: 02-06-2019 Through 07-06-2019",

}

TY - GEN

T1 - Algebras, Graphs and Thetas

AU - De Carli Silva, Marcel K.

AU - Coutinho, Gabriel

AU - Godsil, Chris

AU - Roberson, David E.

N1 - Conference code: 10

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations and 1-walk regular graphs. We further generalize it to a stronger inequality involving the Lovász theta number of such graph, and some theta variants, including characterizations of the equality.

AB - We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations and 1-walk regular graphs. We further generalize it to a stronger inequality involving the Lovász theta number of such graph, and some theta variants, including characterizations of the equality.

KW - Clique-coclique inequality

KW - Coherent configuration

KW - Lovász theta function

KW - Matrix-algebra

U2 - 10.1016/j.entcs.2019.08.025

DO - 10.1016/j.entcs.2019.08.025

M3 - Conference article

AN - SCOPUS:85076255272

SN - 1571-0661

VL - 346

SP - 275

EP - 283

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

T2 - 10th Latin and American Algorithms, Graphs and Optimization Symposium,

Y2 - 2 June 2019 through 7 June 2019

ER -

Algebras, Graphs and Thetas

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this