On the Bruhat order of labeled graphs

Brualdi, Richard A.; Fernandes, Rosário; Furtado, Susana

http://hdl.handle.net/10362/66747

Utilize este identificador para referenciar este registo.

Nome:	Descrição:	Tamanho:	Formato:
Bruhat_graph_part1.pdf		271.38 KB	Adobe PDF	Ver/Abrir

Contacte-nos

Autores

Brualdi, Richard A.

Fernandes, Rosário

Furtado, Susana

Resumo(s)

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.

Descrição

The second author’s work was partially supported by the Fundação para a Ciência e a Tecnologia through the project UID/MAT/00297/2013 . The third author’s work was partially supported by the Fundação para a Ciência e a Tecnologia through the project UID/MAT/04721/2013 .