Bipartite graphs obtained from adjacency matrices of orientations of graphs

AbstractIf G denotes a graph of order n, then the adjacency matrix of an orientation G→ of G can be thought of as the adjacency matrix of a bipartite graph B(G→) of order 2n, where the rows and columns correspond to the bipartition of B(G→). For a graph H, let k(H) denote the number of connected components of H. Set m(G)=min{k(B(G→)):G→ an orientation of G} and M(G) = max{k((G→):G→ an orientation of G}. R.A. Brualdi et al. [1] introduced these ideas and, among other results, proved that for a connected graph G of order n,m(G)=M(G)=n+1 if and only if G is a tree. We prove an intermediate value theorem for k(B(G→)) and investigate the minimum and maximum number of edges possible in a graph G of order n for fixed k((G→)). In particular, we treat the case when G is complete, so that G→ is a tournament