Canadian Mathematical Society
www.cms.math.ca
|          |    |           |    |
|----------|----|-----------|----|
|          | |  |           | |  |
| Site map | |  | CMS store |    |

location:            Publications → journals → CMB
Abstract view

# Asymptotic Existence of Resolvable Graph Designs

Read article
[PDF: 175KB]
http://dx.doi.org/10.4153/CMB-2007-050-x
Canad. Math. Bull. 50(2007), 504-518
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

MSC Classifications:  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]
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8382383584976196, "perplexity_flag": "middle"}