CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Publications        
Abstract view

Asymptotic Existence of Resolvable Graph Designs

  Published:2007-12-01
 Printed: Dec 2007
  • Peter Dukes
  • Alan C. H. Ling
Features coming soon:
Citations   (via CrossRef) Tools: Search Google Scholar:
Format:   HTML   LaTeX   MathJax   PDF   PostScript  

Abstract

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 graph decomposition, resolvable designs
MSC Classifications: 05B05, 05C70, 05B10 show english descriptions Block designs [See also 51E05, 62K10]
Factorization, matching, partitioning, covering and packing
Difference sets (number-theoretic, group-theoretic, etc.) [See also 11B13]
05B05 - Block designs [See also 51E05, 62K10]
05C70 - Factorization, matching, partitioning, covering and packing
05B10 - Difference sets (number-theoretic, group-theoretic, etc.) [See also 11B13]
 

© Canadian Mathematical Society, 2014 : https://cms.math.ca/