Bigraphs versus digraphs via matrices
✍ Scribed by Richard A. Brualdi; Frank Harary; Zevi Miller
- Book ID
- 102892061
- Publisher
- John Wiley and Sons
- Year
- 1980
- Tongue
- English
- Weight
- 949 KB
- Volume
- 4
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
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.