Search

A matroid M has all-graphic cocircuits if M ∖ Y is a graphic matroid for every cocircuit Y ∈ C ∗ ( M ) . In Papalamprou and Pitsoulis (2013) it has been shown that signed-graphic matroids that are representable in G F ( 2 ) can be decomposed into graphic matroids and matroids with all-graphic cocircuits. In this paper we study this class of signed-graphic matroids with all-graphic cocircuits and provide the set of regular excluded minors as well as a complete characterization when the matroid is cographic, which in turn results in a simple recognition algorithm. [ABSTRACT FROM AUTHOR]

Abstract: We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix by finding node-edge incidence matrices and such that . Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called -sums starting from network matrices and their transposes and two compact representation matrices of a certain ten element matroid. Given that are binet matrices we examine the -sums of network and binet matrices. It is shown that the-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for . A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under -sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the -sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix. [Copyright &y& Elsevier]