A Study on Perfect matching Bipartite Graph

Abstract

In this paper, we introduce a corresponding between bipartite graphs with a perfect matching and digraphs, which implicates an equivalent relation between the extendibility of bipartite graphs and the strongly connectivity of digraphs. Such an equivalent relation explains the similar results on k-extendable bipartite graphs and k-strong digraphs. We also study the relation among k-extendable bipartite graphs, k-strong digraphs and combinatorial matrices. For bipartite graphs that are not 1-extendable and digraphs that are not strong, we prove that the elementary components and strong components are counterparts.