Uniform coverings of 2-paths in the complete graph and the complete bipartite graph

Abstract

Let $G$ be a graph and $H$ a subgraph of $G$. A $D(G,H,\lambda )$ design is a collection $\mathcal{D}$ of subgraphs of $G$ each isomorphic to $H$ so that every $2$-path (path of length $2$) in $G$ lies in exactly $\lambda$ subgraphs in $\mathcal{D}$. The problem of constructing $D(K_n,C_n,1)$ designs is the so-called Dudeney’s round table problem. We denote by $C_k$, a cycle on $k$ vertices and by $P_k$, a path on $k$ vertices.

In this paper, we construct $D(K_{n,n},C_{2n},1)$ designs and $D(K_n,P_n,1)$ designs when $n\equiv 0,1,3(\mathrm{mod}4)$; and $D(K_{n,n},C_{2n},2)$ designs and $D(K_n,P_n,2)$ designs when $n\equiv 2(\mathrm{mod}4)$. The existence problems of $D(K_{n,n},C_{2n},1)$ designs and $D(K_n,P_n,1)$ designs for $n\equiv 2(\mathrm{mod}4)$ remain open.