Minimum embedding of any Steiner triple system into a 3-sun system via matchings

Abstract

Let $G$ be a simple finite graph and $G^{\prime }$ be a subgraph of $G$. A $G^{\prime }$-design $(X,\mathcal{B})$ of order $n$ is said to be embedded into a $G$-design $(X\cup U,\mathcal{C})$ of order $n+u$, if there is an injective function $f:\mathcal{B}\to \mathcal{C}$ such that $B$ is a subgraph of $f(B)$ for every $B\in \mathcal{B}$. The function $f$ is called an embedding of $(X,\mathcal{B})$ into $(X\cup U,\mathcal{C})$. If $u$ attains the minimum possible value, then $f$ is a minimum embedding. Here, by means of König's Line Coloring Theorem and edge coloring properties a complete solution is given to the problem of determining a minimum embedding of any $K_3$-design (well-known as Steiner Triple System or, shortly, STS) into a 3-sun system or, shortly, a 3SS (i.e., a $G$-design where $G$ is a graph on six vertices consisting of a triangle with three pendant edges which form a 1-factor).