A necessary and sufficient condition for the total unimodularity of a matrix in terms of graph theory

Abstract

We present a necessary and sufficient condition for an arbitrary matrix A to be totally unimodular. The matrix A is interpreted as the adjacency matrix of a bipartite graph G(A) The total unimodularity of A corresponds to non-existence of a cycle in G(A) which has an odd column valuation and which is equal to the induced subgraph, Some applications of the results are also discussed.

Keywords:

• Total unimodularity
• bipartite graphs
• perfect matching
• multicommodity flow

AMS 1980 Subject Classifications:

• Primary: 90 C 10
• Secondary: 05 C 50
• Secondary: 05 C 38