|
|
Results 1 - 1 of 1 |
1. CMB 2007 (vol 50 pp. 504)
| Asymptotic Existence of Resolvable Graph Designs Let $v \ge k \ge 1$ and $\lam \ge 0$ be integers. A \emph{block
design} $\BD(v,k,\lambda)$ is a collection $\cA$ of $k$-subsets of a
$v$-set $X$ in which every unordered pair of elements from $X$ is
contained in exactly $\lambda$ elements of $\cA$. More generally, for a
fixed simple graph $G$, a \emph{graph design} $\GD(v,G,\lambda)$ is a
collection $\cA$ 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 $\cA$. A famous result of Wilson says that for a
fixed $G$ and $\lambda$, there exists a $\GD(v,G,\lambda)$ for all
sufficiently large $v$ satisfying certain necessary conditions. A
block (graph) design as above is \emph{resolvable} if $\cA$ can be
partitioned into partitions of (graphs whose vertex sets partition)
$X$. Lu has shown asymptotic existence in $v$ of resolvable
$\BD(v,k,\lambda)$, yet for over twenty years the analogous problem for
resolvable $\GD(v,G,\lambda)$ has remained open. In this paper, we settle
asymptotic existence of resolvable graph designs.
Keywords:graph decomposition, resolvable designs Categories:05B05, 05C70, 05B10 |

