A Generalization of Tutte's Characterization of Totally Unimodular Matrices

We characterize the symmetric (0, 1)-matrices that can be signed symmetrically so that every principal submatrix has determinant 0, ±1. This characterization generalizes Tutte's famous characterization of totally unimodular matrices. The result can be viewed as an excluded minor theorem for an...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 1997-05, Vol.70 (1), p.101-117
Main Author: Geelen, J.F.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We characterize the symmetric (0, 1)-matrices that can be signed symmetrically so that every principal submatrix has determinant 0, ±1. This characterization generalizes Tutte's famous characterization of totally unimodular matrices. The result can be viewed as an excluded minor theorem for an interesting class of delta-matroids.
ISSN:0095-8956
1096-0902
DOI:10.1006/jctb.1997.1751