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,
, is decomposed into edge-disjoint copies of a complete graph on three vertices, also referred to as a triple or K3. The first non-arbitrary case of a Steiner Triple System that can be designed is on K7. Since there are seven vertices in the complete graph K7, 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 K9 decomposed into triangles or copies of K3.
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
. A complete graph with a hole can be described as a graph on
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,
. Figure 2 depicts a complete graph with a hole denoted
. K4 is the set of four vertices where each vertex is connected to every other vertex with an edge. The hole (
) is a set of two vertices that are each connected to every vertex in K4, 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
. A
can be described as a complete graph on four vertices, minus one edge. Figure 3 depicts a
, 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
. 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
, we are able to resolve both of these cases.
2. Previous Work
In 1977, Bermond and Schonheim determined that a complete graph
can be decomposed into
’s without having any edges left over if and only if
or 1 mod 5 and
[1]. In 1993, Hoffman, Lindner, Sharry, and Street solved the Maximum Packings Problem of
. Their paper reveals exactly when there is a leave of two or three vertices after the maximum number of
’s are used in the total decomposition of
[2]. Hoffman, Lindner, Sharry, and Street solved the total decomposition of a complete graph using
’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
into
’s when
(Bermond and Schonheim’s decomposition) and when
(Maximum Packings Problem).
3. Preliminary Information
Since there are no edges in V, there are only four types of
blocks. We name these types of blocks:
,
,
, and
as shown in Figure 4. In this paper, we describe a construction using
,
and
type blocks that solves a case where d is even, and where there are additional restrictions on v.
Figure 1. The decomposition of K9 into copies of K3.
Figure 2. A complete graph (K4) with a hole of size 2, denoted K4 + 2.
Figure 4. The four different ways to construct the
.
Since d is even, we let
and envision
as two subsets, where each subset is a complete graph on t vertices,
. These two sets are denoted as
and
, where the vertices in each subset are labeled from 0 to
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
to vertices in
. We refer to all the edges and vertices in and between
and
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,
, the difference of a and b (mod t), can be defined as the smallest non-negative integer congruent to
or
(mod t). Any edge
, in subset
, is defined to be of pure difference
. So, the pure differences in
are
. When t is divisible by two, the edge difference between 0 and
is referred to as the half difference.
Similarly, the edge
between sets
and
is said to be of mixed difference
(Figure 6). Therefore, the mixed differences in
are
. There are t mixed differences.
All edges in
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,
, describes t edges.
Figure 5.
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
and
. Pure Differences describe edges within
and
.
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
or
, 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
design on
.
4.1. Five Must Divide the Total Number of Edges
The number of edges in
must divide the number of edges in
. Since
is a complete graph, there are
edges in
. Furthermore, every vertex in the hole V, is connected to every vertex upstairs, in
. This generates dv more edges. Therefore, altogether, there are
edges in
. Since a
is composed of five edges, and since an edge used in a
may not be reused, the total number of edges,
, must be divisible by five. When
, 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
.
Since the total number of edges in the graph must be divisible by five and
, this paper examines the case when
. When we substitute this value for v in the equation for the total number of edges,
, the result yields
. Therefore, when
, the total number of edges is divisible by five, and both conditions are satisfied.
5. Alpha-Delta Construction
Both
and
blocks are used to decompose
in the
construction. In the Alpha-Delta construction, we consider the case where d is even and
. Since each
block uses exactly two vertices in the hole (V), and since each
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
blocks are not adjacent to any vertices in V and are only used in complete graph
, every edge of the
block is an edge in
. Any remaining edges that are not used by the
blocks, are used in
blocks. In total, there are
blocks and
blocks.
5.1. Bridges
We use bridges to construct the
blocks used in the decomposition of
. 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
base block as depicted below.
Given
, the number of pure differences in each subset of the complete graph is
, 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
, and are stacked in order to maximize the number of bridges. The bridges that use even pure differences are constructed using mixed differences from
to t. An example of an entire bridge construction is pictured in Figure 9.
Figure 8. Conversion from Bridge to
block.
Figure 9. An example of the bridge placement. Each dot represents a mixed difference and each arc represents a pure differences in
.
All the pure differences used in the arcs will be less than or equal to
. Therefore, the half difference,
, will never be used in the bridges, as
. Recall that in this construction, we are only considering the case when a is even. When constructing bridges/
blocks, we are careful to use the same pure differences in each copy of
, in order to ensure that we can use Lemma 1 on the remaining edges. In general, when all bridges are implemented, a total of
mixed differences and
pure differences are saturated.
Each bridge can be translated into a mathematical notation that describes a set of
blocks:
(1)
where
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
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
(2)
The bridges that use even pure differences can be described as:
When
,
(3)
When the notation (1) is applied to the general bridges, every
block is explicitly defined by the following:
Bridges using odd pure differences generate the following blocks:
When
,
(4)
where
and
.
Bridges using even pure differences generate the following blocks:
When
,
(5)
where
and
.
In this way, we partition
into
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
block, uses three mixed differences, and there will always be two mixed differences left over, the number of mixed differences
in
must be greater than or equal to
to ensure that there are enough mixed difference to accommodate the maximum number of
base blocks,
. Since the number of mixed differences is t, or
, we can say
in order to accommodate the maximum amount of
base blocks,
.
Along with ensuring that there are enough mixed differences, there must also be enough pure differences. In general, all of the
base blocks use up
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
. So,
. Therefore,
, and
also holds. Since
(from the mixed differences) is more restrictive on d than
, we need
to ensure there are enough mixed and pure differences for the
construction.
In this way, we have demonstrated how to construct
base blocks, which, when developed (mod t), yield
blocks with
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
blocks. This is the
construction.
5.3. Final Remarks on the Alpha-Delta Construction
The Alpha-Delta Construction results in the following theorem:
Theorem 2 There exists a
design on
when the following conditions hold:
1) d is even.
2)
.
3) a is even.
4)
.
6. Alpha-Delta-Beta Construction
In this construction,
,
, and
blocks are used to decompose
. Similar to the Alpha-Delta construction, the necessary conditions include that d is even, and that
. Unlike the Alpha-Delta construction, three must divide t. In the Alpha-Delta-Beta construction, exactly three
blocks are always used. Each
block is composed of exactly one vertex in V, three vertices in
, and two edges in
of pure difference length one and two. In this way, the three
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
block uses three vertices in
.
Recall that
blocks use exactly two vertices in V and
blocks use no vertices in V. Since
and
blocks always use an even number of vertices in V, and since
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,
blocks and 2t
blocks are exhausted. Any other remaining 1-factors that are not used in
or
blocks will be used in
blocks, where each
block uses one 1-factor. From this, we find that
blocks are used.
6.1. Using Beta Blocks
In the Alpha-Delta-Beta Construction construction,
blocks are formed using edges in
of pure difference length one and two, and three vertices in V. Each
connects a vertex in V with 3 vertices in
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
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
to indicate
or {2}. The
blocks can be found as follows:
(6)
(7)
(8)
Each developed (mod t), where
and
.
6.2. Bridges
The second element of the Alpha-Delta-Beta Construction is the
block. When a is odd,
, where
is the number of
blocks in the con-
struction. Recall from Section 5.1 that each
block can be represented by a bridge. Since the pure differences one and two are used by the
blocks, the smallest odd pure difference the bridges use is three, and the smallest even is four. Since a pure difference from each subset
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
block. If we split
in half to form two equal subset graphs of size t, we can label label vertices
or {2}. Each bridge can then be converted into a
block using the following notation:
(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
blocks in the Alpha-Delta-Beta construction are found as follows:
When
,
(10)
developed (mod t), where
and
.
When
,
(11)
developed (mod t), where
and
.
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
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
blocks. Thus, an arc of length four will leave six (3 × 2) unused mixed differences after all
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
. This is because each
block uses three mixed differences:
, and ten mixed differences remain unused (as mentioned above). Since there are t, or
mixed differences,
to ensure that there are enough mixed differences to accommodate the maximum number of
blocks,
.
Along with ensuring that there are enough mixed differences, we must also ensure there are enough pure differences. In general, a
block contributes to the saturation of one pure difference. This is because each
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
block uses two arcs of the same pure difference length in a single bridge, by the time all
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
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
blocks,
, must always be less than the total amount of pure differences, which we know to be
. So,
. If
is true, then
also holds*. Since
is more restrictive on d than
, we can use
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
design on
when the following conditions hold:
1) d is a multiple of 6.
2)
.
3) a is odd.
4)
.
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
. We also can work to find a
design when a is odd and
, as well as a design when
. In the future, we can also work on the cases when d is odd.