Representations of bicircular matroids

AbstractA bicircular matroid is a matroid defined on the edge set of a graph. Two different graphs can have the same bicircular matroid. The first result of this paper is a characterization of the collection of graphs having the same bicircular matroid as a given arbitrary graph. A bicircular matroid can be represented by a matrix over the real numbers that has at most two nonzeros per column. Such a matrix can be viewed as an incidence matrix of a graph. The second result of this paper is that given almost any (in a sense to be made precise) collection of graphs G1,…,Gt having the same bicircular matroid M, there exist row-equivalent matrices N1,…,Nt each representing M, such that Ni is an incidence matrix of Gi for 1 ≤ i ≤ t. These results form the basis for an algorithm (presented in a subsequent paper) that under certain conditions converts a given linear-programming problem to a generalized-network flow problem