Connectivity and Reducibility of Graphs

Abstract

Corresponding to every graph, bipartite graph, or directed bipartite graph there exists a directed graph which is connected if and only if the original graph is connected.In this paper, it is shown that for every directed graph there exists a certain bipartite graph such that the directed graph is connected if and only if the bipartite graph is irreducible. Other connections between reducibility and connectivity are established.