Asymptotic Existence of Resolvable Graph Designs

Dukes, Peter ; Ling, Alan C. H.

Canadian mathematical bulletin, Tome 50 (2007) no. 4, pp. 504-518

Résumé

Let $v\,\ge \,k\,\ge \,1$ and $\lambda \,\ge \,0$ be integers. A block design $\text{BD}\left( v,\,k,\,\lambda\right)$ is a collection $\mathcal{A}$ of $k$ -subsets of a $v$ -set $X$ in which every unordered pair of elements from $X$ is contained in exactly $\lambda $ elements of $\mathcal{A}$ . More generally, for a fixed simple graph $G$ , a graph design $\text{GD}\left( v,\,G,\,\lambda\right)$ is a collection $\mathcal{A}$ of graphs isomorphic to $G$ with vertices in $X$ such that every unordered pair of elements from $X$ is an edge of exactly $\lambda $ elements of $\mathcal{A}$ . A famous result of Wilson says that for a fixed $ $ and $\lambda $ , there exists a $\text{GD}\left( v,\,G,\,\lambda\right)$ for all sufficiently large $ $ satisfying certain necessary conditions. A block (graph) design as above is resolvable if $\mathcal{A}$ can be partitioned into partitions of (graphs whose vertex sets partition) $X$ . Lu has shown asymptotic existence in $v$ of resolvable $\text{BD}\left( v,\,k,\,\lambda\right)$ , yet for over twenty years the analogous problem for resolvable $\text{GD}\left( v,\,G,\,\lambda\right)$ has remained open. In this paper, we settle asymptotic existence of resolvable graph designs.

Détail

DOI : 10.4153/CMB-2007-050-x

Mots-clés : 05B05, 05C70, 05B10, graph decomposition, resolvable designs