Hostname: page-component-7b7567c8c-lpg2g Total loading time: 0 Render date: 2026-11-15T19:26:35.640Z Has data issue: false hasContentIssue false

Embedding Partial Graph Designs, Block Designs, and Triple Systems with λ > 1

Published online by Cambridge University Press:  20 November 2018

C. J. Colbournt
Affiliation:
Department of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3GL, Canada
R. C. Hamm
Affiliation:
Department of Mathematics, College of Charleston, Charleston, South Carolina, 29424 U.S.A.
C. C. Lindner
Affiliation:
Department of Mathematics, Auburn University, Auburn, Alabama, 36849 U.S.A.
C. C. Lindner
Affiliation:
Department of Mathematics, Auburn University, Auburn, Alabama, 36849 U.S.A.
C. A. Rodger
Affiliation:
Department of Mathematics, Auburn University, Auburn, Alabama, 36849 U.S.A.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A general embedding technique for graph designs and block designs is developed, which transforms the embedding problem for partial designs with ƛ > 1 into the embedding problem for partial designs with ƛ = 1. Given an embedding technique for n-element partial block designs with ƛ = 1 into block designs with f(n) elements, the transformation produces a technique which embeds an «-element partial design with ƛ > 1 and block size k into a design with at most /(3k-1ƛn2) elements. For graph designs and block designs with k > 3, a finite embedding method results. For triple systems, a quadratic embedding technique is obtained immediately; the best previous result here was exponential. Finally, for partial triple systems, Mendelsohn triple systems, and directed triple systems, these quadratic embeddings are improved to linear using a colouring technique.

Keywords

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1986