Bipartite graphs obtained from adjacency matrices of orientations of graphs

✍ Scribed by K.B. Reid

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 630 KB
• Volume: 72
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(88)90222-1

✦ Synopsis

If G denotes a graph of order n, then the adjacency matf;ix 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 agraph H, let k(H) denote the number of connected components of H. Set m(G) = min{k(B(G)): 6 an orientation of G} and M(G) = max{k(B(G):G an orientation of G}. R.A. Brualdi et al. [l] 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 mjnimum 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.