Decomposition of binary signed-graphic matroids

DOI10.1137/100801007MaRDI QIDQ2848529zbMATH OpenOpenAlexFDO

Authors Leonidas Pitsoulis, Konstantinos Papalamprou

Publication date 26 September 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.6497

zbMATH Keywords

decompositionmatroidssigned graphs

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Signed and weighted graphs (05C22) Combinatorial optimization (90C27)

Abstract: In this paper we employ Tutte's theory of bridges to derive a decomposition theorem for binary matroids arising from signed graphs. The proposed decomposition differs from previous decomposition results on matroids that have appeared in the literature in the sense that it is not based on $k$-sums, but rather on the operation of deletion of a cocircuit. Specifically, it is shown that certain minors resulting from the deletion of a cocircuit of a binary matroid will be graphic matroids apart from exactly one that will be signed-graphic, if and only if the matroid is signed-graphic.

Recommendations

• Signed-graphic matroids with all-graphic cocircuits
• Binary signed-graphic matroids: representations and recognition algorithms
• Regular matroid decomposition via signed graphs
• A decomposition theory for matroids. I: General results
• On Tutt's Characterization of graphic matroids—a graphic proof

Cited in

(12)

• Decomposition of binary matroids
• Binary signed-graphic matroids: representations and recognition algorithms
• Signed-graphic matroids with all-graphic cocircuits
• A Tutte decomposition for matrices and bimatroids
• On characterizing the class of cographic signed-graphic matroids
• Rank decompositions and signed bigraphs
• Regular matroid decomposition via signed graphs
• Recognition algorithms for binary signed-graphic matroids
• On the basis pair graphs of signed-graphic matroids
• Decomposition of quaternary signed-graphic matroids
• A mathematical programming approach for recognizing binet matrices
• Symplectic spaces and ear-decomposition of matroids

This page was built for publication: Decomposition of binary signed-graphic matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848529)