Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-08T12:23:21.606Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  20 November 2018

C. J. Colbournt ,
R. C. Hamm ,
C. C. Lindner ,
C. C. Lindner  and
C. A. Rodger
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

05B0505B15
Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 29 , Issue 4 , 01 December 1986 , pp. 385 - 391
Copyright
Copyright © Canadian Mathematical Society 1986

References

1. Andersen, L. D., Hilton, A. J. W., and Mendelson, E., Embedding partial Steiner triple systems, Proc. London Math. Soc. 41 (1980) pp. 557–576.Google Scholar
2. Colbourn, C. J. and Colbourn, M. J., The computational complexity of decomposing block designs, Annals of Discrete Mathematics, 27 (1985) pp. 315–350.Google Scholar
3. Colbourn, C.J., Hamm, R. C., and Rodger, C. A., Small embeddings of partial directed triple systems and partial triple systems with even λ, Journal of Combinational Theory A, 37 (1984) pp. 363 — 369.Google Scholar
4. Colbourn, C. J. and Harms, J. J., Directing triple systems, Ars Combinatoria 15 (1983) pp. 261–266.Google Scholar
5. Evans, T. and Lindner, C.C., Finite Embedding Theorems for Partial Designs and Algebras, Séminaires des Mathématiques Supérieures, Université de Montréal, 1971.Google Scholar
6. Ganter, B., Partialpairwise balanced designs, in Colloquio Internazionale sulle Teorie Combinatorie, Roma 1973, pp. 377–380.Google Scholar
7. Hamm, R. C., Embedding theorems for triple systems, Ph.D. thesis, Department of Mathematics, Auburn University, Auburn AL, 1983.Google Scholar
8. Hamm, R. C., Lindner, C. C., and Rodger, C. A., Linear embeddings of partial directed triple systems with λ = 1 and partial triple systems with λ = 2, Ars Combinatoria 16 (1983) pp. 11 — 16.Google Scholar
9. Holyer, I., The NP'-completeness of some edge-partition problems, SIAM Journal on Computing 10 (1981) pp. 713–717.Google Scholar
10. Lindner, C.C., A survey of embedding theorems for Steiner systems, Annals of Discrete Mathematics 7 (1980) pp. 175–202.Google Scholar
11. Lindner, C. C. and Rosa, A., Finite embedding theorems for partial triple systems with λ > I, Ars Combinatoria 1 (1976) pp. 159–166.+I,+Ars+Combinatoria+1+(1976)+pp.+159–166.>Google Scholar
12. Wilson, R. M., Construction and uses of pairwise balanced designs, Math. Centre Tracts 55 (1974) pp. 18–41.Google Scholar