Bigraphs versus digraphs via matrices

It was observed by Dulmage and Mendelsohn in their work on matrix reducibility that there is a one‐to‐one correspondence between bigraphs and digraphs determined by the utilization of the adjacency matrix. In this semiexpository paper we explore the interaction between this correspondence and a theory of matrix decomposability that is developed in several different articles. These results include: (a) a characterization of those bipartite graphs that can be labeled so that the resulting digraph is symmetric; (b) a criterion for the bigraph of a symmetric digraph to be connected; (c) a necessary and sufficient condition for a square binary matrix to be fully indecomposable in terms of its associated bigraph, and (d) matrix criteria for a digraph to be strongly, unilaterally, or weakly connected. We close with an unsolved extermal problem on the number of components of the bigraph of various orientations of a given graph. This leads to new amusing characterizations of trees and bigraphs. Dedicated to the graph‐theoretic partnership of Lloyd Dulmage and Nathan Mendelsohn.