On 2k-twisted graphs (Q1101125)

The paper is to formalize the notion of the number of twists in a chain in a directed graph and then to generalize a theorem on strongly connected graphs to graphs. A chain in a directed graph is obtained by putting a pointer at a vertex and moving it in the direction or against the direction of a connected sequence of arcs to another vertex. Each change of direction is a twist, hence the notion of a k-twisted chain. Likewise, a 2k-twisted graph is a graph such that for every pair of vertices there exists a 2k-twisted closed chain through the given vertices. It is shown that for a 2k-twisted graph the set of algebraic 2k-twisted cycles is an integral spanning set for the integral flow module of the graph. Since a graph is 0-twisted if and only if it is strongly connected, the result generalizes the well-known theorem that there is a basis for the flow space of a strongly connected graph consisting of algebraic circuits.