Graph representations of a bicircular matroid
详细信息 查看全文
文摘
The bicircular matroid B(G) of a graph G is known to be a transversal matroid. There are, in general, many graphs that represent the matroid as well as many presentations. We discuss the graphs that represent the same bicircular matroid. Given any presentation of a bicircular matroid, we show how to find a graph representing the matroid, and that, in some cases, there is more than one such graph. In the first four sections, we describe background and pertinent results on bicircular matroids. Many of the lemmas and theorems in these sections have straightforward proofs but these results have not been previously stated. In the final section, we illustrate how the graph constructed via the techniques developed by Brualdi and Neudauer (Quart. J. Math. Oxford (2) 48 (1997) 17) for finding the minimal presentations of a bicircular matroid, combined with the earlier results of this paper, relate to the operations developed by Coullard et al. (Discrete Appl. Math. 32 (1991) 223).