Algebras, Graphs and Thetas

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

Research output: Contribution to journalConference articleResearchpeer-review

52 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 languageEnglish
JournalElectronic Notes in Theoretical Computer Science
Volume346
Pages (from-to)275-283
ISSN1571-0661
DOIs
Publication statusPublished - 1 Jan 2019
Event10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019 - Belo Horizonte, Brazil
Duration: 2 Jun 20197 Jun 2019

Conference

Conference10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019
CountryBrazil
CityBelo Horizonte
Period02/06/201907/06/2019

Keywords

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

Cite this