Graph Divisible Designs and Packing Constructions

We introduce a generalization of group divisible designs and offer example applications to challenging problems in design theory. The generalization considers edge-decompositions of joins of arbitrary graphs, whereas group divisible designs handle only joins of edgeless graphs. Our example construct...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2015-11, Vol.31 (6), p.2181-2191
Main Authors: Dukes, Peter J., Ling, Alan C. H.
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a generalization of group divisible designs and offer example applications to challenging problems in design theory. The generalization considers edge-decompositions of joins of arbitrary graphs, whereas group divisible designs handle only joins of edgeless graphs. Our example constructions include: (1) optimal packings with block size five for the previously unsettled congruence class v ≡ 13 ( mod 20 ) ; (2) an optimal grooming with with ratio seven for the previously unsettled congruence class v ≡ 56 ( mod 84 ) ; and (3) a constructive ‘quadratic’ embedding of partial designs with block size four.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-014-1518-x