Geodesic
Embedding Partial Graph Designs, Block Designs, and Triple Systems with λ > 1
Canadian mathematical bulletin, Tome 29 (1986) no. 4, pp. 385-391

Voir la notice de l'article provenant de la source Cambridge University Press

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.
DOI : 10.4153/CMB-1986-061-4
Mots-clés : 05B05, 05B15 
Colbournt, C. J.; Hamm, R. C.; Lindner, C. C.; Lindner, C. C.; Rodger, C. A. Embedding Partial Graph Designs, Block Designs, and Triple Systems with λ > 1. Canadian mathematical bulletin, Tome 29 (1986) no. 4, pp. 385-391. doi: 10.4153/CMB-1986-061-4
@article{10_4153_CMB_1986_061_4,
     author = {Colbournt, C. J. and Hamm, R. C. and Lindner, C. C. and Lindner, C. C. and Rodger, C. A.},
     title = {Embedding {Partial} {Graph} {Designs,} {Block} {Designs,} and {Triple} {Systems} with \ensuremath{\lambda} > 1},
     journal = {Canadian mathematical bulletin},
     pages = {385--391},
     year = {1986},
     volume = {29},
     number = {4},
     doi = {10.4153/CMB-1986-061-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1986-061-4/}
}
TY  - JOUR
AU  - Colbournt, C. J.
AU  - Hamm, R. C.
AU  - Lindner, C. C.
AU  - Lindner, C. C.
AU  - Rodger, C. A.
TI  - Embedding Partial Graph Designs, Block Designs, and Triple Systems with λ > 1
JO  - Canadian mathematical bulletin
PY  - 1986
SP  - 385
EP  - 391
VL  - 29
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1986-061-4/
DO  - 10.4153/CMB-1986-061-4
ID  - 10_4153_CMB_1986_061_4
ER  - 
%0 Journal Article
%A Colbournt, C. J.
%A Hamm, R. C.
%A Lindner, C. C.
%A Lindner, C. C.
%A Rodger, C. A.
%T Embedding Partial Graph Designs, Block Designs, and Triple Systems with λ > 1
%J Canadian mathematical bulletin
%D 1986
%P 385-391
%V 29
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1986-061-4/
%R 10.4153/CMB-1986-061-4
%F 10_4153_CMB_1986_061_4

[1] 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] 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] 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] 4. Colbourn, C. J. and Harms, J. J., Directing triple systems, Ars Combinatoria 15 (1983) pp. 261–266. Google Scholar

[5] 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] 6. Ganter, B., Partialpairwise balanced designs, in Colloquio Internazionale sulle Teorie Combinatorie, Roma 1973, pp. 377–380. Google Scholar

[7] 7. Hamm, R. C., Embedding theorems for triple systems, Ph.D. thesis, Department of Mathematics, Auburn University, Auburn AL, 1983. Google Scholar

[8] 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] 9. Holyer, I., The NP'-completeness of some edge-partition problems, SIAM Journal on Computing 10 (1981) pp. 713–717. Google Scholar

[10] 10. Lindner, C.C., A survey of embedding theorems for Steiner systems, Annals of Discrete Mathematics 7 (1980) pp. 175–202. Google Scholar

[11] 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] 12. Wilson, R. M., Construction and uses of pairwise balanced designs, Math. Centre Tracts 55 (1974) pp. 18–41. Google Scholar

Cité par Sources :