Algebras, graphs and thetas

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

Use este identificador para citar ou linkar para este item: http://hdl.handle.net/1843/74100

Tipo:	Artigo de Periódico
Título:	Algebras, graphs and thetas
Título(s) alternativo(s):	Álgebras, gráficos e tetas
Autor(es):	Marcel K. de Carli Silva Gabriel de Morais Coutinho Chris Godsil David E. Roberson
Resumo:	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.
Assunto:	Teoria dos Grafos Álgebra Linear
Idioma:	eng
País:	Brasil
Editor:	Universidade Federal de Minas Gerais
Sigla da Instituição:	UFMG
Departamento:	ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
Tipo de Acesso:	Acesso Aberto
Identificador DOI:	https://doi.org/10.1016/j.entcs.2019.08.025
URI:	http://hdl.handle.net/1843/74100
Data do documento:	2019
metadata.dc.url.externa:	https://www.sciencedirect.com/science/article/pii/S1571066119300751
metadata.dc.relation.ispartof:	Electronic Notes in Theoretical Computer Science
Aparece nas coleções:	Artigo de Periódico

Arquivos associados a este item:

Arquivo	Descrição	Tamanho	Formato
Algebras, Graphs and Thetas.pdfA.pdf		162.41 kB	Adobe PDF	Visualizar/Abrir

Mostrar registro completo do item Visualizar estatísticas