Flows on the join of two graphs. (English) Zbl 1289.05197

Summary: The join of two graphs \(G\) and \(H\) is a graph formed from disjoint copies of \(G\) and \(H\) by connecting each vertex of \(G\) to each vertex of \(H\). We determine the flow number of the resulting graph. More precisely, we prove that the join of two graphs admits a nowhere-zero \(3\)-flow except for a few classes of graphs: a single vertex joined with a graph containing an isolated vertex or an odd circuit tree component, a single edge joined with a graph containing only isolated edges, a single edge plus an isolated vertex joined with a graph containing only isolated vertices, and two isolated vertices joined with exactly one isolated vertex plus some number of isolated edges.


05C21 Flows in graphs
Full Text: DOI Link