A Decomposition of a Complete Graph with a Hole

Roxanne Back^1*, Alejandra Brewer Castano¹, Rachel Galindo¹, Jessica Finocchiaro²

¹Florida Southern College, Lakeland, USA.
²University of Colorado, Boulder, USA.

DOI: 10.4236/ojdm.2021.111001                

Abstract

In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a . A complete graph with a hole, , consists of a complete graph on d vertices, , and a set of independent vertices of size v, V, where each vertex in V is adjacent to each vertex in . When d is even, we give two constructions for the decomposition of a complete graph with a hole into copies of  : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting d and v so that  , we are able to resolve both of these cases for a subset of using difference methods and 1-factors.

Keywords

Graph Decomposition, Combinatorial Design, Complete Graph with a Hole

1. Introduction

The Steiner Triple System is the most renowned problem in the study of design theory. In a Steiner Triple System, a complete graph on d vertices, $K_d$, is decomposed into edge-disjoint copies of a complete graph on three vertices, also referred to as a triple or K₃. The first non-arbitrary case of a Steiner Triple System that can be designed is on K₇. Since there are seven vertices in the complete graph K₇, we can label each vertex {0, 1, 2, 3, 4, 5, 6}. The set of triples {{0, 1, 3}, {1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {0, 4, 5}, {1, 5, 6}, {0, 2, 6}} forms the Steiner Triple System of order seven. A Steiner Triple System can also be considered a complete graph partitioned into a set of triangles. Figure 1 depicts a Steiner Triple System on nine vertices, i.e. a K₉ decomposed into triangles or copies of K₃.

Similar to the Steiner Triple System, in this paper, we decompose a graph into subgraphs; however, we decompose complete graphs that contain a hole—also referred to as $K_d+v$. A complete graph with a hole can be described as a graph on $d+v$ vertices where each vertex in an independent set of vertices of size v (the hole), is adjacent to every vertex in a complete graph on d vertices, $K_d$. Figure 2 depicts a complete graph with a hole denoted $K_4+2$. K₄ is the set of four vertices where each vertex is connected to every other vertex with an edge. The hole ( $v=2$ ) is a set of two vertices that are each connected to every vertex in K₄, but share no edges with any elements in the hole.

In our work, we decompose a complete graph with a hole into isomorphic copies of $K_4-e$. A $K_4-e$ can be described as a complete graph on four vertices, minus one edge. Figure 3 depicts a $K_4-e$, where {a, b, c, d} represent four vertices, and where the only two vertices that are not adjacent are c and d.

In this paper, we give two constructions for the decomposition of a complete graph with a hole into $K_4-e$. We call these the Alpha-Delta Construction and the Alpha-Beta-Delta Construction. By restricting d so that it is even and v so that $v=2\left(d-1\right)-5a$, we are able to resolve both of these cases.

2. Previous Work

In 1977, Bermond and Schonheim determined that a complete graph $K_n$ can be decomposed into $K_4-e$ ’s without having any edges left over if and only if $n\equiv 0$ or 1 mod 5 and $n\ge 6$ [1]. In 1993, Hoffman, Lindner, Sharry, and Street solved the Maximum Packings Problem of $K_n$. Their paper reveals exactly when there is a leave of two or three vertices after the maximum number of $K_4-e$ ’s are used in the total decomposition of $K_n$ [2]. Hoffman, Lindner, Sharry, and Street solved the total decomposition of a complete graph using $K_4-e$ ’s in both cases: with a leave of two and a leave of three vertices. However, they did not use the idea of a hole in either solution. If we reinterpret each of the aforementioned discoveries to incorporate a hole, we can envision vertices that are left over after the decomposition to be vertices in the hole. In this way, we can guarantee solutions to the decomposition of $K_d+v$ into $K_4-e$ ’s when $v=0,1$ (Bermond and Schonheim’s decomposition) and when $v=2,3$ (Maximum Packings Problem).

3. Preliminary Information

Since there are no edges in V, there are only four types of $K_4-e$ blocks. We name these types of blocks: $\alpha$, $\beta$, $\gamma$, and $\delta$ as shown in Figure 4. In this paper, we describe a construction using $\alpha$, $\beta$ and $\delta$ type blocks that solves a case where d is even, and where there are additional restrictions on v.

Figure 1. The decomposition of K₉ into copies of K₃.

Figure 2. A complete graph (K₄) with a hole of size 2, denoted K₄ + 2.

Figure 3. A $K_4-e$.

Figure 4. The four different ways to construct the $K_4-e$.

Since d is even, we let $d=2t$ and envision $K_d$ as two subsets, where each subset is a complete graph on t vertices, $K_t$. These two sets are denoted as ${\mathbb{Z}}_t\times \left\{1\right\}$ and ${\mathbb{Z}}_t\times \left\{2\right\}$, where the vertices in each subset are labeled from 0 to $t-1$ and all possible edges connect vertices between the two subsets. Figure 5 depicts a complete graph with a hole when d is even. In Figure 5, the hash marks between the two sub sets represent the edges that connect vertices from ${\mathbb{Z}}_t\times \left\{1\right\}$ to vertices in ${\mathbb{Z}}_t\times \left\{2\right\}$. We refer to all the edges and vertices in and between ${\mathbb{Z}}_t\times \left\{1\right\}$ and ${\mathbb{Z}}_t\times \left\{2\right\}$ as upstairs and the vertices in V, the hole, as downstairs (Figure 5).

3.1. Pure and Mixed Differences

If a and b are integers, ${\left|b-a\right|}_t$, the difference of a and b (mod t), can be defined as the smallest non-negative integer congruent to $b-a$ or $a-b$ (mod t). Any edge $a_1{b}_1$, in subset ${\mathbb{Z}}_t$, is defined to be of pure difference ${\left|b-a\right|}_t$. So, the pure differences in $K_d$ are $0\le {\left|b-a\right|}_t\le \lfloor \frac{t}{2}\rfloor$. When t is divisible by two, the edge difference between 0 and $\frac{t}{2}$ is referred to as the half difference.

Similarly, the edge $a_1{b}_2$ between sets ${\mathbb{Z}}_t\times \left\{1\right\}$ and ${\mathbb{Z}}_t\times \left\{2\right\}$ is said to be of mixed difference ${\left|b-a\right|}_t$ (Figure 6). Therefore, the mixed differences in $K_d$ are $0\le {\left|b-a\right|}_t\le t-1$. There are t mixed differences.

All edges in $K_d$ can be described with either a mixed or pure difference. Each mixed difference describes a set of t edges. Every pure difference describes a set of 2t edges, and when t is divisible by two, the half difference, $\frac{t}{2}$, describes t edges.

Figure 5. $K_d+v$ when d is even is split into two subsets, where edges and vertices between the two complete graphs are the upstairs, and vertices in v are the downstairs.

Figure 6. Mixed Differences describe edges between ${\mathbb{Z}}_t\times \left\{1\right\}$ and ${\mathbb{Z}}_t\times \left\{2\right\}$. Pure Differences describe edges within ${\mathbb{Z}}_t\times \left\{1\right\}$ and ${\mathbb{Z}}_t\times \left\{2\right\}$.

3.2. Stern/Lenz

The two main tools we use in our designs are difference methods and 1-factors. A 1-factor is a perfect matching, that is, a set of single edges that contains each vertex exactly once. When the edges of a graph are partitioned into a set of 1-factors, this is called a 1-factorization. In a paper by Stern and Lenz, they prove the following lemma [3].

Lemma 1 Let G be a simple regular graph and G’ be an isomorphic copy of G. Form the graph H by adding an edge between each vertex in G and its isomorphic mate in G’. Then H, the graph shown below in Figure 7, has a 1-factorization.

To ensure the use of this lemma, every time we use a pure difference from one subset, either ${\mathbb{Z}}_t\times \left\{1\right\}$ or ${\mathbb{Z}}_t\times \left\{2\right\}$, we will use the same pure difference from the other subset. We will also ensure at least one mixed difference remains unused so that the lemma can still be applied.

4. Necessary Conditions

In this section, we present the conditions necessary to construct a $K_4-e$ design on $K_d+v$.

4.1. Five Must Divide the Total Number of Edges

The number of edges in $K_4-e$ must divide the number of edges in $K_d+v$. Since $K_d$ is a complete graph, there are $\frac{d\left(d-1\right)}{2}$ edges in $K_d$. Furthermore, every vertex in the hole V, is connected to every vertex upstairs, in $K_d$. This generates dv more edges. Therefore, altogether, there are $\frac{d\left(d-1\right)}{2}+dv$ edges in $K_d+v$. Since a $K_4-e$ is composed of five edges, and since an edge used in a $K_4-e$ may not be reused, the total number of edges, $\frac{d\left(d-1\right)}{2}+dv$, must be divisible by five. When $\mathrm{5\; <mo>\; |\; </mo>}d$, this condition will be met.

Figure 7. A simple regular graph that has a 1-factorization.

4.2. Necessary Condition for v

All blocks use at least one edge upstairs. Therefore, the number of blocks must be less than or equal to the number of edges upstairs. This simplifies to $v\le 2\left(d-1\right)$.

Since the total number of edges in the graph must be divisible by five and $v\le 2\left(d-1\right)$, this paper examines the case when $v=2\left(d-1\right)-5a$. When we substitute this value for v in the equation for the total number of edges, $\frac{d\left(d-1\right)}{2}+dv$, the result yields $5d\left(\frac{d-1}{2}-a\right)$. Therefore, when $v=2\left(d-1\right)-5a$, the total number of edges is divisible by five, and both conditions are satisfied.

5. Alpha-Delta Construction

Both $\alpha$ and $\delta$ blocks are used to decompose $K_d+v$ in the $\alpha /\delta$ construction. In the Alpha-Delta construction, we consider the case where d is even and $v=2\left(d-1\right)-5a$. Since each $\alpha$ block uses exactly two vertices in the hole (V), and since each $\delta$ block uses zero vertices in the hole, we consider the case where v is even. In order to ensure that v remains even, a must be even, as well.

In the Alpha-Delta construction, since $\delta$ blocks are not adjacent to any vertices in V and are only used in complete graph $K_d$, every edge of the $\delta$ block is an edge in $K_d$. Any remaining edges that are not used by the $\delta$ blocks, are used in $\alpha$ blocks. In total, there are $\frac{ta}{2}$ $\delta$ blocks and $t\left(2t-\frac{5}{2}a-1\right)$ $\alpha$ blocks.

5.1. Bridges

We use bridges to construct the $\delta$ blocks used in the decomposition of $K_d+v$. Each bridge has five components, three points, each representing a mixed difference, and two arcs, each representing a pure difference (see Figure 8). Each bridge corresponds to a $\delta$ base block as depicted below.

Given $t=\frac{d}{2}$, the number of pure differences in each subset of the complete graph is $\lfloor \frac{t}{2}\rfloor$, and the number of mixed differences is t. The bridges are constructed graphically by listing the mixed differences and connecting them with two arcs, where lengths of each represent pure differences. The bridges that use odd pure differences are constructed first, using the mixed differences from 0 to $\lfloor \frac{t}{2}\rfloor$, and are stacked in order to maximize the number of bridges. The bridges that use even pure differences are constructed using mixed differences from $\lfloor \frac{t}{2}\rfloor$ to t. An example of an entire bridge construction is pictured in Figure 9.

Figure 8. Conversion from Bridge to $K_4-e$ block.

Figure 9. An example of the bridge placement. Each dot represents a mixed difference and each arc represents a pure differences in $K_d+v$.

All the pure differences used in the arcs will be less than or equal to $\frac{a}{2}$. Therefore, the half difference, $\frac{t}{2}$, will never be used in the bridges, as $\frac{a}{2}<\frac{t}{2}$. Recall that in this construction, we are only considering the case when a is even. When constructing bridges/ $\delta$ blocks, we are careful to use the same pure differences in each copy of ${\mathbb{Z}}_t$, in order to ensure that we can use Lemma 1 on the remaining edges. In general, when all bridges are implemented, a total of $3\left(\frac{a}{2}\right)$ mixed differences and $\frac{a}{2}$ pure differences are saturated.

Each bridge can be translated into a mathematical notation that describes a set of $\delta$ blocks:

$\left(\left(0+k\mathrm{,1}\right)\mathrm{,}\left(b+k\mathrm{,2}\right)\mathrm{,}\left(c+k\mathrm{,2}\right)\mathrm{,}\left(\left(b-a\right)+k\mathrm{,1}\right)\right)$ (1)

where $0\le k\le \left(t-1\right)$ and where a, b, and c are the respective labels of the mixed differences in the bridge construction.

An image of the construction of one bridge (a, b, c), and how it can be converted into a $\delta$ block, can be found in Figure 8.

As shown in Figure 8, each bridge takes the form of (a, b, c). Bridges that are made using odd pure differences can be described as:

When $0\le i\le \lceil \frac{a}{4}\rceil -1$

$\left(\left(\lceil \frac{a}{4}\rceil -i-1\right)\mathrm{,}\left(\lceil \frac{a}{4}\rceil +i\right)\mathrm{,}\left(3\lceil \frac{a}{4}\rceil -i-1\right)\right)$ (2)

The bridges that use even pure differences can be described as:

When $1\le j\le \lfloor \frac{a}{4}\rfloor$,

$\left(\left(3\lceil \frac{a}{4}\rceil +\lfloor \frac{a}{4}\rfloor -j\right)\mathrm{,}\left(3\lceil \frac{a}{4}\rceil +\lfloor \frac{a}{4}\rfloor +j\right)\mathrm{,}\left(3\left(\frac{a}{2}\right)-j+2\right)\right)$ (3)

When the notation (1) is applied to the general bridges, every $\delta$ block is explicitly defined by the following:

Bridges using odd pure differences generate the following blocks:

When $2\le 2i\le \frac{a}{2}$,

$\left(\left(0+k\mathrm{,1}\right)\mathrm{,}\left(3\lceil \frac{a}{4}\rceil +\lfloor \frac{a}{4}\rfloor +k+i\mathrm{,2}\right)\mathrm{,}\left(3\frac{a}{2}+2+k-i\mathrm{,2}\right)\mathrm{,}\left(2i+k\mathrm{,1}\right)\right)$ (4)

where $i\in \mathbb{Z}$ and $0\le k\le \left(t-1\right)$.

Bridges using even pure differences generate the following blocks:

When $1\le 2j+2\le \frac{a}{2}$,

$\left(\left(0+k\mathrm{,1}\right)\mathrm{,}\left(\lceil \frac{a}{4}\rceil +k+j\mathrm{,2}\right)\mathrm{,}\left(3\lceil \frac{a}{4}\rceil -1+k-j\mathrm{,2}\right)\mathrm{,}\left(2j+1+k\mathrm{,1}\right)\right)$ (5)

where $j\in \mathbb{Z}$ and $0\le k\le \left(t-1\right)$.

In this way, we partition $K_d+v$ into $\frac{a}{2}$ $\delta$ base blocks that are then developed mod t to complete the decomposition.

5.2. Ensuring Conditions Are Satisfied

Recall that in order to apply Lemma 1, there must be at least one unused mixed difference. This construction guarantees at least two unused mixed differences—one from under each arc of length two. For example, in Figure 9, mixed differences 11 and 14 are not connected with an arc of pure difference length; thus, Lemma 1 can still be applied. Additionally, we must ensure that there are enough pure and mixed differences available to build the necessary number of blocks. Since each bridge, or $\delta$ block, uses three mixed differences, and there will always be two mixed differences left over, the number of mixed differences

in $K_d+v$ must be greater than or equal to $3\left(\frac{a}{2}\right)+2$ to ensure that there are enough mixed difference to accommodate the maximum number of $\delta$ base blocks, $\frac{a}{2}$. Since the number of mixed differences is t, or $\frac{d}{2}$, we can say $d\ge 3a+4$ in order to accommodate the maximum amount of $\delta$ base blocks, $\left(\frac{d}{2}\right)$.

Along with ensuring that there are enough mixed differences, there must also be enough pure differences. In general, all of the $\delta$ base blocks use up $\frac{a}{2}$ pure differences in total. Therefore, in order to ensure that there are enough pure differences, the number of bridges must always be less than the total amount of pure differences, which we know to be $\lfloor \frac{t}{2}\rfloor$. So, $\frac{a}{2}<\lfloor \frac{t}{2}\rfloor$. Therefore, $\frac{a}{2}<\lfloor \frac{d}{4}\rfloor$, and $d>2a$ also holds. Since $d\ge 3a+4$ (from the mixed differences) is more restrictive on d than $d>2a$, we need $d\ge 3a+4$ to ensure there are enough mixed and pure differences for the $\alpha /\delta$ construction.

In this way, we have demonstrated how to construct $\frac{a}{2}$ $\delta$ base blocks, which, when developed (mod t), yield $\frac{ta}{2}$ $\delta$ blocks with $5t\left(t-5-\frac{5a}{2}\right)$ edges left over. Since the conditions of Lemma 1 have been met, we are ensured a 1-factorization of the remaining edges. As a result, the remaining differences can be used entirely in $t\left(2t-\frac{5}{2}a-1\right)$ $\alpha$ blocks. This is the $\alpha /\delta$ construction.

5.3. Final Remarks on the Alpha-Delta Construction

The Alpha-Delta Construction results in the following theorem:

Theorem 2 There exists a $K_4-e$ design on $K_d+v$ when the following conditions hold:

1) d is even.

2) $v=2\left(d-1\right)-5a$.

3) a is even.

4) $d\ge 3a+4$.

6. Alpha-Delta-Beta Construction

In this construction, $\alpha$, $\beta$, and $\delta$ blocks are used to decompose $K_d+v$. Similar to the Alpha-Delta construction, the necessary conditions include that d is even, and that $v=2\left(d-1\right)-5a$. Unlike the Alpha-Delta construction, three must divide t. In the Alpha-Delta-Beta construction, exactly three $\beta$ blocks are always used. Each $\beta$ block is composed of exactly one vertex in V, three vertices in ${\mathbb{Z}}_t$, and two edges in ${\mathbb{Z}}_t$ of pure difference length one and two. In this way, the three $\beta$ blocks used in this construction saturate three vertices in V and all edges of pure difference one and two. In order to ensure that all edges of pure difference one and two in the graph are saturated, it is a necessary condition that t is divisible by three, since each $\beta$ block uses three vertices in ${\mathbb{Z}}_t$.

Recall that $\alpha$ blocks use exactly two vertices in V and $\delta$ blocks use no vertices in V. Since $\alpha$ and $\delta$ blocks always use an even number of vertices in V, and since $\beta$ blocks always use three vertices in V, there will always be an odd number of vertices depleted in the hole. Thus, a must be odd to ensure that all vertices in the hole are saturated, as a is related to the number of blocks. This is another difference from the Alpha-Delta construction, where a is even. In this

construction, $t\left(\frac{a-1}{2}\right)$ $\delta$ blocks and 2t $\beta$ blocks are exhausted. Any other remaining 1-factors that are not used in $\delta$ or $\beta$ blocks will be used in $\alpha$ blocks, where each $\alpha$ block uses one 1-factor. From this, we find that $t\left(2t-1-4a+3\left(\frac{a-1}{2}\right)\right)$ $\alpha$ blocks are used.

6.1. Using Beta Blocks

In the Alpha-Delta-Beta Construction construction, $\beta$ blocks are formed using edges in $K_d$ of pure difference length one and two, and three vertices in V. Each $\beta$ connects a vertex in V with 3 vertices in ${\mathbb{Z}}_t$ partitioned into three parallel classes. Each class contains t/3 disjoint sets of size 3. These sets of size 3, along with a single vertex in V, will create a $\beta$ block using an edge of pure difference 1 and 2. Each of the three classes uses t/3 edges of each difference 1 and 2 therefore exhausting all 2t edges of these differences. Let $l=1,2$ to indicate ${\mathbb{Z}}_t\times \left\{1\right\}$ or {2}. The $\beta$ blocks can be found as follows:

$\left(\left(\mathrm{0,3}\right)\mathrm{,}\left(0+3k\mathrm{,}l\right)\mathrm{,}\left(1+3k\mathrm{,}l\right)\mathrm{,}\left(2+3k\mathrm{,}l\right)\right)$ (6)

$\left(\left(\mathrm{1,3}\right)\mathrm{,}\left(1+3k\mathrm{,}l\right)\mathrm{,}\left(2+3k\mathrm{,}l\right)\mathrm{,}\left(3+3k\mathrm{,}l\right)\right)$ (7)

$\left(\left(\mathrm{2,3}\right)\mathrm{,}\left(2+3k\mathrm{,}l\right)\mathrm{,}\left(3+3k\mathrm{,}l\right)\mathrm{,}\left(4+3k\mathrm{,}l\right)\right)$ (8)

Each developed (mod t), where $k\in \mathbb{Z}$ and $0\le k\le \frac{t}{3}$.

6.2. Bridges

The second element of the Alpha-Delta-Beta Construction is the $\delta$ block. When a is odd, $\Delta =\frac{a-1}{2}$, where $\Delta$ is the number of $\delta$ blocks in the con-

struction. Recall from Section 5.1 that each $\delta$ block can be represented by a bridge. Since the pure differences one and two are used by the $\beta$ blocks, the smallest odd pure difference the bridges use is three, and the smallest even is four. Since a pure difference from each subset ${\mathbb{Z}}_t$ must be used, each pure difference is used twice. This leaves at least ten mixed differences unused.

Like the Alpha-Delta Construction, each bridge can be translated into a $\delta$ block. If we split $K_d$ in half to form two equal subset graphs of size t, we can label label vertices ${\mathbb{Z}}_t\times \left\{1\right\}$ or {2}. Each bridge can then be converted into a $\delta$ block using the following notation:

$\left(\left(\mathrm{0,1}\right)\mathrm{,}\left(b\mathrm{,2}\right)\mathrm{,}\left(c\mathrm{,2}\right)\mathrm{,}\left(b-a\mathrm{,1}\right)\right)$ (9)

where a, b, and c are the respective labels of the mixed differences in the bridge construction.

When this notation is applied to the general bridges, the $\delta$ blocks in the Alpha-Delta-Beta construction are found as follows:

When $3\le 2j+3\le \lceil \frac{a+2}{2}\rceil$,

$\begin{array}{l}(\left(\mathrm{0,1}\right)\mathrm{,}\left(\lceil \frac{a-2}{4}\rceil +2+k+j\mathrm{,2}\right)\mathrm{,}\left(3\lceil \frac{a-1}{4}\rceil +3+k-j\mathrm{,2}\right)\mathrm{,}\\ \left(\lceil \frac{a-2}{4}\rceil +\lceil \frac{a-1}{4}\rceil +3+k+2j\mathrm{,1}\right))\end{array}$ (10)

developed (mod t), where $j\in \mathbb{Z}$ and $0\le k\le \left(t-1\right)$.

When $4\le 2i+2\le \lceil \frac{a+2}{2}\rceil$,

$\begin{array}{l}(\left(\mathrm{0,1}\right)\mathrm{,}\left(3\lceil \frac{a-1}{4}\rceil +\lfloor \frac{a-1}{4}\rfloor +6+k+i\mathrm{,2}\right)\mathrm{,}\\ \left(3\frac{a+1}{2}+7+k-i\mathrm{,2}\right)\mathrm{,}\left(2+k+2i\mathrm{,1}\right))\end{array}$ (11)

developed (mod t), where $i\in \mathbb{Z}$ and $0\le k\le \left(t-1\right)$.

6.3. Ensuring Conditions Are Satisfied

In order for Lemma 1.1 apply, there must be at least one unused mixed difference; however, in this construction, there will be at least ten unused mixed differences. This is because the smallest, even pure difference is four, and an arc of length four will leave three mixed differences unused. Because every pure difference other than the half difference generates two 1-factors, the $\delta$ blocks use arcs of each pure difference length twice to saturate the two 1-factors generated by one pure difference. In other words, each pure difference appears twice in the $\delta$ blocks. Thus, an arc of length four will leave six (3 × 2) unused mixed differences after all $\delta$ blocks are implemented. Moreover, the smallest odd pure difference used in the bridges is three. One arc of pure difference length three leaves two mixed differences unused. Two arcs of length three will leave four unused mixed differences. Therefore, in total, there will be at least ten unused mixed differences.

To ensure there are enough mixed differences for the Alpha-Delta-Beta construction the number of mixed differences, t, must be less than $3a+17$. This is because each $\delta$ block uses three mixed differences: $\left(3\left(\frac{a-1}{2}\right)\right)$, and ten mixed differences remain unused (as mentioned above). Since there are t, or $\frac{d}{2}$ mixed differences, $d\ge 3a+17$ to ensure that there are enough mixed differences to accommodate the maximum number of $\delta$ blocks, $\left(\frac{a-1}{2}\right)$.

Along with ensuring that there are enough mixed differences, we must also ensure there are enough pure differences. In general, a $\delta$ block contributes to the saturation of one pure difference. This is because each $\delta$ block uses five 1-factors, two of which are generated by pure differences. Because one pure difference generates two 1-factors, using two 1-factors of the same pure difference value use up one pure difference. Although not every $\delta$ block uses two arcs of the same pure difference length in a single bridge, by the time all $\delta$ blocks are implemented, all arcs will have used an arc of each pure difference length twice. For this reason, we can say that, generally, each $\delta$ block uses up two 1-factors generated by pure differences, and thus, one entire pure difference. In order to ensure that there are enough pure differences in the construction, the total number of $\delta$ blocks, $\Delta$, must always be less than the total amount of pure differences, which we know to be $\lfloor \frac{t}{2}\rfloor$. So, $\frac{a-1}{2}<\lfloor \frac{d}{4}\rfloor$. If $\frac{a-1}{2}<\lfloor \frac{d}{4}\rfloor$ is true, then $d>2a+6$ also holds*. Since $d\ge 3a+17$ is more restrictive on d than $d>2a+6$, we can use $d\ge 3a+17$ to ensure there are enough mixed and pure differences for the Alpha-Delta-Beta construction.

6.4. Final Remarks on the Alpha-Delta-Beta Construction

The Alpha-Delta-Beta Construction results in the following theorem:

There exists a $K_4-e$ design on $K_d+v$ when the following conditions hold:

1) d is a multiple of 6.

2) $v=2\left(d-1\right)-5a$.

3) a is odd.

4) $d\ge 3a+17$.

7. Future Work

In our future work, we will complete the case when d is not divisible by 5 and a is even, as well as when $d\le 3a+4$. We also can work to find a $K_4-e$ design when a is odd and $5|d$, as well as a design when $10|d$. In the future, we can also work on the cases when d is odd.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bermond, J.C. and Schonheim, J. (1977) G-Decomposition of , Where G Has Four Vertices or Less. Discrete Mathematics, 54, 113-126.
[2]	Hoffman, D.G., Lindner, C.C., Sharry, M.J. and Street, A.P. (1996) Maximum Packing of with Copies of . Aequationes Mathematicae, 51, 247-269.
[3]	Stern, G. and Lenz, H. (1980) Steiner Triple Systems with Given Subspaces: Another Proof of the Doyen-Wilson Theorem. Bolletino dell Unione Matematica Italiana, 17, 109-114.