Electronic Journal of Graph Theory and Applications 12 .
, 289Ae295 Embedding partial 3-star designs Matt Noblea .
Shayne Nochumsonb Department of Mathematics and Statistics.
Middle Georgia State University.
Macon.
GA 31206.
b Department of Mathematics and Statistics.
Auburn University.
Auburn.
AL 36849.
noble@mga.
edu, snk0018@auburn.
Abstract Define a 3-star decomposition of Kn as being a collection of subgraphs, each isomorphic to K1,3 , with the property that each edge of Kn appears in exactly one of the subgraphs.
A partial 3star decomposition is similarly defined except each edge appears in at most one of the subgraphs.
In this work, it is shown that any partial 3-star decomposition of Kn can be embedded into a decomposition of Kn s where s O 4.
Furthermore, we determine, for any maximal partial 3star decomposition P of Kn , the minimum s OO .
, 2, 3, .
such that P can be embedded into a decomposition of Kn s .
Keywords: graph decompositions, embedding partial graph decompositions, stars Mathematics Subject Classification: 05B99 DOI: 10.
5614/ejgta.
Introduction All graphs will be simple and finite.
Define a k-star to be the complete bipartite graph K1,k .
A k-star decomposition of the complete graph Km consists of a collection B of subgraphs, each isomorphic to K1,k , with the property that each edge of Km appears in exactly one of the subgraphs.
A partial k-star decomposition P of Kn is similarly defined except each edge appears in at most one of the subgraphs.
If P OI B, say that P is embeddable in B, or alternately that B is Received: 11 December 2018.
Revised: 16 June 2024.
Accepted: 21 July 2024.
Embedding partial 3-star designs Noble and S.
Nochumson an embedding of P.
We will designate by G0 the graph formed by deleting from Kn all edges found in any subgraph of P, where in various literature G0 is termed the leave of the partial Furthermore, it is free to assume in our work that P is maximal Ae that is, all vertices of the corresponding G0 have degree less than k.
We will be primarily concerned with the case k = 3, and although the graph K1,3 is commonly called a AuclawAy, we will refer to it as being a 3-star to keep with the terminology used in .
In .
Hoffman and Roberts prove that, regardless of the value of n, any partial k-star decomposition of Kn can be embedded into a k-star decomposition of Kn s where s is at most 7k Oe 4 if k is odd, and 8k Oe 4 if k is even.
These bounds are lowered by the authors in .
, where it is shown that such an s can be selected which is at most 3k Oe 2 for k odd and 4k Oe 2 for k even.
Bounds on s are lowered even further in .
, where De Vas Gunasekara and Horsley prove that s can be chosen Oo satisfying s < 4 k when k is odd and s < .
Oe 2 .
k when k is even.
Furthermore, it is shown in .
that those bounds are optimal in the sense that they cannot be improved for general k.
In our work, we consider the specific case of k = 3, showing that s = 4 is a sharp upper bound.
We conclude by determining, for each maximal partial 3-star decomposition P, the minimum s OO .
, 2, 3, .
such that P is embeddable into some decomposition of Kn s .
Preliminaries Our method of proof will be constructive and we illustrate it with the following example.
Consider the partial decomposition P of K6 given in Figure 1, where G0 has edge set .
1 v5 , v1 v6 , v3 v4 }.
Figure 1.
A Partial 3-Star Decomposition of K6 Consider the adjacency matrix of G0 , looking only at the triangular portion of the matrix below the main diagonal.
The edges of the original copy of K6 are in bijective correspondence with the cells of this portion of the matrix.
Form a AustaircaseAy diagram by coloring any cell containing a 0 and making blank any cell containing a 1, as is done in Figure 2.
Three cells in such a diagram correspond to the edges of a 3-star if and only if they appear in the same row, or they appear in the same column, or they appear in rows and columns that intersect in a cell on the main diagonal of the adjacency matrix.
In particular, since any partial 3-star decomposition we are considering can be assumed maximal, each column of a staircase diagram for a potential G0 can have zero, one, or two blank cells only.
Embedding partial 3-star designs Noble and S.
Nochumson Figure 2.
The Staircase Diagram for the Partial Decomposition Given in Figure 1 In forming an embedding of P, we extend the diagram by affixing s additional rows, for some s OO .
, 2, 3, .
, which represent the additional vertices x1 , .
, xs .
For our example, it turns out that s = 3 does the trick.
For each additional row, we take note of the number of cells in that row computed modulo 3.
In the staircase diagram for G0 , for each column containing one blank cell, we may then extend our partial decomposition by coloring that blank cell along with two blank cells simultaneously lying in that column and in the affixed rows.
We call such a maneuver a 2drop as we are AudroppingAy two colored cells into the additional rows.
Similarly, for each column in the G0 diagram containing two blank cells, we may color those cells along with one cell lying in that column and in an additional row.
Refer to this move as a 1-drop.
Returning to our example, these moves are executed in Figure 3.
Figure 3.
An Extended Staircase Diagram for the Partial Decomposition Given in Figure 1 Note that, in Figure 3, after the described 1- and 2-drops have been made, the remaining numbers of uncolored cells in the rows corresponding to vertices x1 , x2 , and x3 are each congruent to 0 modulo 3.
What remains to be seen .
nd what we intend to show in the next sectio.
is that this process of designating 1-drops and 2-drops can always be performed with a suitable s OO .
, 2, 3, .
so that all cells are colored in the original diagram for G0 , and the number of uncolored cells in each additional row is congruent to 0 modulo 3.
This circumstance allows us to complete our decomposition of Kn s by iteratively coloring sets of three cells, with each set consisting of three Embedding partial 3-star designs Noble and S.
Nochumson cells lying in the same additional row.
Results Throughout this section, we will use the fact that |E(Kn )| O 0 .
if n O 0 or 1 .
and |E(Kn )| O 1 .
if n O 2 .
Theorem 3.
Let n O 0 or 1 .
A partial 3-star decomposition P of Kn is embeddable in a 3-star decomposition of Kn 3 .
Proof.
Assume P maximal, and consider a staircase diagram of G0 .
Let 1 designate the number of columns in the diagram having one blank cell, and denote by 2 the number of columns having two blank cells.
Since P is only a partial decomposition, we have 1 2 > 0.
Also, since |E(Kn )| O 0 .
, we must have 1 22 O 0 .
, which implies 1 O 2 .
Affix three additional rows to the staircase diagram and note that the number of cells in these three rows will be congruent to 0, 1, and 2 .
, respectively, with the order of those depending on whether n O 0 .
or n O 1 .
Regardless, labeling the additional rows R1 .
R2 .
R3 , and letting ri be the total number of empty cells in row Ri , we may assume r1 O 1 .
, r2 O 2 .
, and r3 O 0 .
We now consider cases.
Case 1.
1 O 2 O 1 .
We have 1 2-drops to make and 2 1-drops to make.
Place all 2-drops in rows R1 and R2 , along with placing all 1-drops in row R2 .
Case 2.
1 O 2 O 2 .
Place all 2-drops in rows R1 and R2 .
Place all 1-drops in row R1 .
Case 3.
1 O 2 O 0 .
Since 1 2 > 0, here we must have 1 and 2 at least 3.
Place one 1-drop in row R1 and the rest in R2 .
Place all 2-drops in rows R1 and R2 .
Theorem 3.
Let n O 2 .
A partial 3-star decomposition P of Kn is embeddable in a 3-star decomposition of Kn 4 .
Proof.
Assume P maximal, and define 1 and 2 as in the proof of Theorem 3.
Consider a staircase diagram of G0 .
As |E(Kn )| O 1 .
, we have 1 22 O 1 .
, which can be expressed as 1 O 2 1 .
Affix four additional rows R1 .
R2 .
R3 .
R4 to the staircase diagram, and for i OO .
, 2, 3, .
, let ri designate the number of empty cells in row Ri before any AudropsAy have been made.
Note that r1 O 2 .
, r2 O 0 .
, r3 O 1 .
, and r4 O 2 .
Also, when it is advantageous, we may select a column which has no blank cells in the G0 diagram .
he column corresponding to vn , for exampl.
and color three cells that simultaneously lie in that column and in three of the additional rows.
This maneuver, a Au3-dropAy using the terminology we have introduced, will play a factor in the cases that follow.
Case 1.
1 O 1 .
, 2 O 0 .
Here we have 1 2-drops, 2 1-drops, and optional access to at least one 3-drop.
Our plan will then be to place the 3-drop in rows R1 .
R3 , and R4 .
Place all 2-drops in rows R1 and R4 .
Place all 1-drops in row R1 .
Embedding partial 3-star designs Noble and S.
Nochumson Case 2.
1 O 2 .
, 2 O 1 .
Place all 2-drops in rows R1 and R4 .
Place all 1-drops in row R3 .
Case 3.
1 O 0 .
, 2 O 2 .
Again, place a 3-drop in rows R1 .
R3 , and R4 .
Place all 2-drops in rows R1 and R2 .
Conclude by placing one 1-drop in row R1 and the rest in row R4 .
The above two theorems establish an upper bound for the minimum s such that any partial 3-star decomposition of Kn can be embedded into a decomposition of Kn s .
To see that s = 4 cannot be lowered, we need only observe the theorem below, originally proved by Yamamoto, et .
, and also seen as a consequence of more general results of Tarsi in .
Theorem 3.
The complete graph Kn admits a k-star decomposition if and only if |E(Kn )| O 0 .
and n Ou 2k.
It then stands that a partial k-star decomposition of K2 , wherein P would be empty, cannot be embedded into a k-star decomposition of Kn for any n < 2k.
For the general problem studied in .
, this gives a lower bound on the minimum s such that P can be embedded into a k-star decomposition of Kn s , with the bound being s = 2k Oe 2.
However, for our case of k = 3, we were able to determine, for any given P, exactly the minimum s OO .
, 2, 3, .
We do this in the following two theorems.
Theorem 3.
Let P be a maximal partial 3-star decomposition of Kn .
Then P can be embedded into a decomposition of Kn 1 if and only if the following hold.
n O 0 or 2 .
Each component of G0 is an isolated vertex, an even cycle, or a path with an odd number of Proof.
The first condition is obvious as it ensures |E(Kn 1 )| is a multiple of 3.
To see that the second condition is sufficient, place a new vertex x, making it adjacent to every vertex of G0 .
Let C2r be a cycle of G0 with vertices c1 , .
, c2r , and let P2s 1 be a path of G0 with vertices p1 , .
, p2s 1 .
Consider every other vertex of C2r Ae that is, c1 , c3 , .
, c2rOe1 and for each, identify a 3-star of G0 .
centered at that vertex.
Consider vertices p2 , p4 , .
, p2s of the path and for each of these, identify a 3-star centered at that vertex.
Repeat this process for any other even cycles or odd paths in G0 .
The only edges of G0 .
not appearing in any of these identified 3-stars each have x as one of their endpoints.
We can then complete the decomposition of G0 .
through use of 3-stars centered at x.
For necessity, suppose that G0 contains an odd cycle C2r 1 .
When attempting to decompose G0 .
, note that any edge of C2r 1 must appear in a 3-star centered at a vertex of the cycle.
However, any such 3-star contains two edges of C2r 1 , and it follows that all 2r 1 edges cannot appear in a decomposition of G0 .
Now suppose that G0 contains a path P2s .
The same argument applies, as P2s contains an odd number of edges, and any 3-star of G0 .
contains either zero or two edges of P2s .
Theorem 3.
Let P be a maximal partial 3-star decomposition of Kn .
Then P can be embedded into a decomposition of Kn 2 if and only if the following hold.
Embedding partial 3-star designs Noble and S.
Nochumson .
n O 1 or 2 .
G0 has at least one vertex of degree 2.
Proof.
The first condition ensures |E(Kn 2 )| is a multiple of 3.
For necessity of the second condition, assume G0 has only vertices of degree 0 or 1, and consider a potential decomposition of G0 K2 where V (K2 ) = .
, .
Any edge e = ab of G0 must appear in a 3-star centered at a or Removing from G0 K2 all such 3-stars centered at vertices of G0 , we are left with a graph G1 in which deg.
= deg.
and x, y are the only vertices of degree greater than 2.
Consequently, any further 3-stars in G1 must be centered at x or y.
Without loss of generality, assume that in the decomposition, edge e = xy appears in a 3-star centered at x.
It then follows that, in G1 , deg.
O 0 .
This implies deg.
Oe 1 O 0 .
, giving us a contradiction.
For sufficiency of the second condition, let v1 OO V (G0 ) where deg.
1 ) = 2.
We again consider a staircase diagram of G0 and note that the leftmost column has two blank cells.
Affix two additional rows to the diagram labeled R1 and R2 where again, r1 , r2 denote the total number of empty cells in the corresponding row.
Define 1 and 2 as is done in the proofs of Theorems 3.
1 and 3.
Case 1.
n O 1 .
We have 1 O 2 .
with r1 O 1 .
and r2 O 2 .
As we only have two additional rows, we are forced to place all 2-drops in rows R1 and R2 .
If 2 O 1 .
, place all 1-drops in row R2 .
If 2 O 2 .
, instead place all 1-drops in row R1 .
And if 2 O 0 .
hich necessarily implies 2 Ou .
, place one 1-drop in row R1 and the rest in row R2 .
Case 2.
n O 2 .
Here, 1 O 2 1 .
, r1 O 2 .
, and r2 O 0 .
Again, we are forced to place all 2-drops in rows R1 and R2 .
If 2 O 1 .
, place all 1-drops in row R2 .
If instead 2 O 2 .
, place all 1-drops in row R1 .
And if 2 O 0 .
hich again means 2 Ou .
, place one 1-drop in row R1 and the rest in row R2 .
Finally, we note that for any n O 2 .
, there indeed exists a partial 3-star decomposition P of Kn that requires s Ou 4 to embed P into a 3-star decomposition of Kn s .
To see this, in light of the previous two theorems, we just need to find P in which G0 has each vertex of degree less than 2.
For n = 2, this is obvious.
For n = 5, we have the partial 3-star decomposition given in Figure 4.
Figure 4.
A Partial 3-star Decomposition of K5 Embedding partial 3-star designs Noble and S.
Nochumson If n Ou 8, label the vertices of Kn as v1 , .
, vn , and by Theorem 3.
3, there exists a 3-star decomposition of the induced subgraph of Kn on vertices v1 , .
, vnOe1 .
We have deg.
n ) O 1 .
so we can remove 3-stars centered at vn until only one edge remains.
References