Premium
Steiner triple systems with two disjoint subsystems
Author(s) -
Bryant Darryn,
Horsley Daniel
Publication year - 2006
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20071
Subject(s) - combinatorics , mathematics , steiner system , disjoint sets , vertex (graph theory) , graph , order (exchange) , group (periodic table) , discrete mathematics , chemistry , organic chemistry , finance , economics
It is shown that there exists a triangle decomposition of the graph obtained from the complete graph of order v by removing the edges of two vertex disjoint complete subgraphs of orders u and w if and only if u,w , and v are odd, ${{v}\choose 2}-{u\choose 2}- {w\choose 2}\equiv 0$ (mod 3), and ${v}\ge w + u +{\rm max} \{ u,w\}$ . Such decompositions are equivalent to group divisible designs with block size 3, one group of size u , one group of size w , and v – u – w groups of size 1. This result settles the existence problem for Steiner triple systems having two disjoint specified subsystems, thereby generalizing the well‐known theorem of Doyen and Wilson on the existence of Steiner triple systems with a single specified subsystem. © 2005 Wiley Periodicals, Inc. J Combin Designs