Minimum embedding of Steiner triple systems into (K4 - e)-designs II

Alan C H Ling, Charles Colbourn, Gaetano Quattrocchi

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


A (K4 - e)-design of order v + w embeds a given Steiner triple system if there is a subset of v points on which the graphs of the design induce the blocks of the original Steiner triple system. It has been established that w ≥ v / 3, and that when equality is met, such a minimum embedding of an STS(v) exists, except when v = 15. Equality only holds when v ≡ 15, 27 (mod 30). One natural question is: What is the smallest order w such that some STS(v) can be embedded into a (K4 - e)-design of order v + w? We solve the problem for 7 of the 10 congruence classes modulo 30.

Original languageEnglish (US)
Pages (from-to)400-411
Number of pages12
JournalDiscrete Mathematics
Issue number2
StatePublished - Jan 28 2009


  • Embedding

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Minimum embedding of Steiner triple systems into (K4 - e)-designs II'. Together they form a unique fingerprint.

Cite this