On the Bruhat order of labeled graphs.

Abstract 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. [ABSTRACT FROM AUTHOR]