Uniform coverings of 2-paths with 4-cycles
For a graph \(G\) and a subgraph \(H\) of \(G\), a \(D(G, H, \Lambda)\) design is a multiset \(D\) of subgraphs of \(G\), each of which is isomorphic to \(H\) so that every path of length 2 lies in exactly \(\Lambda\) subgraphs in \(D\). Likewise, for a digraph \(G\) and a subgraph \(H\) of \(G\), a \(D(G, H, \Lambda)\) design is a multiset \(D\) of subgraphs of \(G\), each of which is isomorphic to \(H\) so that every directed path of length 2 lies in exactly \(\Lambda\) subgraphs in \(D\). These designs are referred to as Dudeney designs. The paper shows that for \(n \geq 2\) and \(\Lambda \geq 1\) there exists a Dudeney design for the \(2n\)-node complete bipartite graph with cycle of length 4 if and only if (i) \(n\) is even, or (ii) \(n\) is odd and \(\Lambda\) is even. It is also shown that for \(n \geq 2\) and \(\Lambda \geq 1\), there exists a Dudeney design for the \(2n\)-node complete bipartite digraph with directed cycle of length 4.
scientific article; zbMATH DE number 6520419