Algebras, graphs and thetas

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

Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/74100

Type:	Artigo de Periódico
Title:	Algebras, graphs and thetas
Other Titles:	Álgebras, gráficos e tetas
Authors:	Marcel K. de Carli Silva Gabriel de Morais Coutinho Chris Godsil David E. Roberson
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´asz theta number of such graph, and some theta variants, including characterizations of the equality.
Abstract:	Estendemos a desigualdade clique-coclique, anteriormente conhecida por ser válida para grafos em esquemas de associação e grafos transitivos de vértice, para grafos em configurações coerentes homogêneas e grafos regulares de 1 passeio. Nós generalizá-lo ainda mais para uma desigualdade mais forte envolvendo o número teta de Lov´asz de tal gráfico, e alguns variantes teta, incluindo caracterizações da igualdade.
Subject:	Teoria dos Grafos Álgebra Linear
language:	eng
metadata.dc.publisher.country:	Brasil
Publisher:	Universidade Federal de Minas Gerais
Publisher Initials:	UFMG
metadata.dc.publisher.department:	ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
Rights:	Acesso Aberto
metadata.dc.identifier.doi:	https://doi.org/10.1016/j.entcs.2019.08.025
URI:	http://hdl.handle.net/1843/74100
Issue Date:	2019
metadata.dc.url.externa:	https://www.sciencedirect.com/science/article/pii/S1571066119300751
metadata.dc.relation.ispartof:	Electronic Notes in Theoretical Computer Science
Appears in Collections:	Artigo de Periódico

Files in This Item:

File	Description	Size	Format
Algebras, Graphs and Thetas.pdfA.pdf		162.41 kB	Adobe PDF	View/Open

Show full item record