×

A conjecture on small embeddings of partial Steiner triple systems. (English) Zbl 1001.05025

C. C. Lindner and T. Evans [Finite embedding theorems for partial designs and algebras (Séminaire de Mathématiques Supérieures 56, Les Presses de l’Université de Montréal) (1977; Zbl 0363.05017)] conjectured that any partial Steiner triple system of order \(u\) can be embedded in a Steiner triple system of order \(v\) if \(v \geq 2u+1\) and \(v \equiv 1,3 {\pmod 6}\). To date this conjecture remains unresolved. In this paper the author presents a conjecture that implies the above conjecture, and which also has implications for embeddings of order \(v < 2u+1\). A partial Steiner triple system of order \(u\) with leave \(L\) can be embedded in a Steiner triple system of order \(v = u+w\) if and only if there is a \(K_3\)-decomposition of \(L \vee K_w\). The author proves a lemma that establishes necessary conditions for the existence of such \(K_3\)-decompositions. His conjecture is that these necessary conditions are also sufficient. He backs this up by proving several supporting results, including the fact that the conjecture holds for graphs \(L\) with maximum degree at most \(2\) in the case \(w < u+1\). This result yields necessary and sufficient conditions for embeddings of partial Steiner triple systems of order \(u\) with leaves having maximum degree 2 in Steiner triple systems of order \(v < 2u+1\).

MSC:

05B07 Triple systems

Citations:

Zbl 0363.05017
Full Text: DOI

References:

[1] Andersen, J London Math Soc 41 pp 557– (1980)
[2] and On the completion of latin rectangles to symmetric latin squares, (submitted). · Zbl 1051.05013
[3] Colbourn, J Combin Th Ser A 35 pp 100– (1983)
[4] Colbourn, Discrete Math 45 pp 165– (1983)
[5] Colbourn, Graphs and Combinatorics 2 pp 317– (1986)
[6] and Triple Systems, Clarendon Press, Oxford (1999) pp 185-198.
[7] Doyen, Discrete Math 5 pp 229– (1973)
[8] Lindner, J Combin Th Ser A 18 pp 349– (1975)
[9] and Finite embedding theorems for partial designs and algebras, SMS 56, Les Presses de l’Université de Montréal, (1977).
[10] Mendelsohn, Congr Numer 40 pp 235– (1983)
[11] Treash, J Combin Theory Ser A 10 pp 259– (1971)
[12] Vizing, Analiz 3 pp 25– (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.