On the Bruhat order of labeled graphs

• Tipo: Artigo em Revista Científica Internacional
• Data: 2019

Autores

Brualdi, RA (Autor) Outra; Fernandes, R (Autor) Outra; Susana Borges Furtado (Autor) FEP

Revista

Título: Discrete Applied Mathematics

Vol. 258

Páginas: 49-64

ISSN: 0166-218X

Editora: Elsevier

Indexação

ISI Web of Knowledge - 11 Citações

Scopus - 11 Citações

Outras Informações

ID Authenticus: P-00P-YM0

DOI: 10.1016/j.dam.2018.10.039

Abstract (EN): We investigate two Bruhat (partial) orders on graphs with vertices labeled 1, 2, ..., n and with a specified degree sequence R, equivalently, symmetric (0, 1)-matrices with zero trace and a specified row sum vector R (adjacency matrices of such graphs). One is motivated by the classical Bruhat order on permutations while the other one, more restrictive, is defined by a switch of a pair of disjoint edges. In the Bruhat order, one seeks to concentrate the edges of a graph with a given degree sequence among the vertices with smallest labels, thereby producing a minimal graph in this order. We begin with a discussion of graphs whose isomorphism class does not change under a switch. Then we are interested in when the two Bruhat orders are identical. For labeled graphs of regular degree k, we show that the two orders are identical for k <= 2 but not for k = 3.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 16