Embedding partial 3-star designs

Matt Noble^a , Shayne Nochumson^b

^aDepartment of Mathematics and Statistics, Middle Georgia State University, Macon, GA 31206, U.S.A. ^bDepartment of Mathematics and Statistics, Auburn University, Auburn, AL 36849, U.S.A.

matthew.noble@mga.edu, snk0018@auburn.edu

Define a 3-star decomposition of Kⁿ as being a collection of subgraphs, each isomorphic to K1,3, with the property that each edge of Kⁿ appears in exactly one of the subgraphs. A partial 3 star 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 Kⁿ can be embedded into a decomposition of Kn+^s where s ≤ 4. Furthermore, we determine, for any maximal partial 3 star decomposition P of Kn, the minimum s ∈ {1, 2, 3, 4} 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.2024.12.2.9

1. 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 K^m consists of a collection B of subgraphs, each isomorphic to K1,k, with the property that each edge of K^m appears in exactly one of the subgraphs. A partial k-star decomposition P of Kⁿ is similarly defined except each edge appears in at most one of the subgraphs. If P ⊆ 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.

an embedding of \(\mathscr{P}\). We will designate by \(G_0\) the graph formed by deleting from \(K_n\) all edges found in any subgraph of \(\mathscr{P}\), where in various literature \(G_0\) is termed the leave of the partial decomposition. Furthermore, it is free to assume in our work that \(\mathscr{P}\) is maximal – that is, all vertices of the corresponding \(G_0\) have degree less than k. We will be primarily concerned with the case k=3, and although the graph \(K_{1,3}\) is commonly called a "claw", we will refer to it as being a 3-star to keep with the terminology used in [2].

In [2], Hoffman and Roberts prove that, regardless of the value of n, any partial k-star decomposition of \(K_n\) can be embedded into a k-star decomposition of \(K_{n+s}\) where s is at most 7k-4 if k is odd, and 8k-4 if k is even. These bounds are lowered by the authors in [3], where it is shown that such an s can be selected which is at most 3k-2 for k odd and 4k-2 for k even. Bounds on s are lowered even further in [1], where De Vas Gunasekara and Horsley prove that s can be chosen satisfying \(s < \frac{9}{4}k\) when k is odd and \(s < (6-2\sqrt{2})k\) when k is even. Furthermore, it is shown in [1] 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 \(\mathscr{P}\), the minimum \(s \in \{1,2,3,4\}\) such that \(\mathscr{P}\) is embeddable into some decomposition of \(K_{n+s}\).

2. Preliminaries

Our method of proof will be constructive and we illustrate it with the following example. Consider the partial decomposition \(\mathscr{P}\) of \(K_6\) given in Figure 1, where \(G_0\) has edge set \(\{v_1v_5, v_1v_6, v_3v_4\}\).

Figure 1. A Partial 3-Star Decomposition of \(K_6\)

Consider the adjacency matrix of \(G_0\), looking only at the triangular portion of the matrix below the main diagonal. The edges of the original copy of \(K_6\) are in bijective correspondence with the cells of this portion of the matrix. Form a "staircase" 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 \(G_0\) can have zero, one, or two blank cells only.

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 ∈ {1, 2, 3, 4}, 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 2 drop as we are "dropping" two colored cells into the additional rows. Similarly, for each column in the G⁰ 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 x³ are each congruent to 0 modulo 3. What remains to be seen (and what we intend to show in the next section) is that this process of designating 1-drops and 2-drops can always be performed with a suitable s ∈ {1, 2, 3, 4} 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

cells lying in the same additional row.

3. Results

Throughout this section, we will use the fact that |E(Kn)| ≡ 0 (mod 3) if n ≡ 0 or 1 (mod 3) and |E(Kn)| ≡ 1 (mod 3) if n ≡ 2 (mod 3).

Theorem 3.1. Let n ≡ 0 or 1 (mod 3). A partial 3-star decomposition P of Kⁿ is embeddable in a 3-star decomposition of Kn+3.

Proof. Assume P maximal, and consider a staircase diagram of G0. Let α¹ designate the number of columns in the diagram having one blank cell, and denote by α² the number of columns having two blank cells. Since P is only a partial decomposition, we have α¹ + α² > 0. Also, since |E(Kn)| ≡ 0 (mod 3), we must have α¹ + 2α² ≡ 0 (mod 3), which implies α¹ ≡ α² (mod 3). 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 (mod 3), respectively, with the order of those depending on whether n ≡ 0 (mod 3) or n ≡ 1 (mod 3). Regardless, labeling the additional rows R1, R2, R3, and letting rⁱ be the total number of empty cells in row Rⁱ , we may assume r¹ ≡ 1 (mod 3), r² ≡ 2 (mod 3), and r³ ≡ 0 (mod 3). We now consider cases.

Case 1. α¹ ≡ α² ≡ 1 (mod 3)

We have α¹ 2-drops to make and α² 1-drops to make. Place all 2-drops in rows R¹ and R2, along with placing all 1-drops in row R2.

Case 2. α¹ ≡ α² ≡ 2 (mod 3)

Place all 2-drops in rows R¹ and R2. Place all 1-drops in row R1.

Case 3. α¹ ≡ α² ≡ 0 (mod 3)

Since α¹ + α² > 0, here we must have α¹ and α² at least 3. Place one 1-drop in row R¹ and the rest in R2. Place all 2-drops in rows R¹ and R2.

Theorem 3.2. Let n ≡ 2 (mod 3). A partial 3-star decomposition P of Kⁿ is embeddable in a 3-star decomposition of Kn+4.

Proof. Assume P maximal, and define α¹ and α² as in the proof of Theorem 3.1. Consider a staircase diagram of G0. As |E(Kn)| ≡ 1 (mod 3), we have α¹ + 2α² ≡ 1 (mod 3), which can be expressed as α¹ ≡ α² + 1 (mod 3). Affix four additional rows R1, R2, R3, R⁴ to the staircase diagram, and for i ∈ {1, 2, 3, 4}, let rⁱ designate the number of empty cells in row Rⁱ before any "drops" have been made. Note that r¹ ≡ 2 (mod 3), r² ≡ 0 (mod 3), r³ ≡ 1 (mod 3), and r⁴ ≡ 2 (mod 3). Also, when it is advantageous, we may select a column which has no blank cells in the G⁰ diagram (the column corresponding to vn, for example) and color three cells that simultaneously lie in that column and in three of the additional rows. This maneuver, a "3-drop" using the terminology we have introduced, will play a factor in the cases that follow.

Case 1. α¹ ≡ 1 (mod 3), α² ≡ 0 (mod 3)

Here we have α¹ 2-drops, α² 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 R¹ and R4. Place all 1-drops in row R1.

Case 2. α¹ ≡ 2 (mod 3), α² ≡ 1 (mod 3)

Place all 2-drops in rows R¹ and R4. Place all 1-drops in row R3.

Case 3. \[\alpha_1 \equiv 0 \pmod{3}\], \(\alpha_2 \equiv 2 \pmod{3}\)

Again, place a 3-drop in rows R1, R3, and R4. Place all 2-drops in rows R¹ and R2. Conclude by placing one 1-drop in row R¹ 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 Kⁿ 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 al. [6], and also seen as a consequence of more general results of Tarsi in [4] and [5].

Theorem 3.3. The complete graph Kⁿ admits a k-star decomposition if and only if |E(Kn)| ≡ 0 (mod k) and n ≥ 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 Kⁿ for any n < 2k. For the general problem studied in [2], 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 − 2. However, for our case of k = 3, we were able to determine, for any given P, exactly the minimum s ∈ {1, 2, 3, 4} needed. We do this in the following two theorems.

Theorem 3.4. 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.

• (i) n ≡ 0 or 2 (mod 3)
• (ii) Each component of G⁰ is an isolated vertex, an even cycle, or a path with an odd number of vertices.

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 C2^r be a cycle of G⁰ with vertices c1, . . . , c2r, and let P2s+1 be a path of G⁰ with vertices p1, . . . , p2s+1. Consider every other vertex of C2^r – that is, c1, c3, . . . , c2r−¹ and for each, identify a 3-star of G⁰ +{x} centered at that vertex. Consider vertices p2, p4, . . . , p2^s 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 G⁰ + {x} not appearing in any of these identified 3-stars each have x as one of their endpoints. We can then complete the decomposition of G⁰ + {x} through use of 3-stars centered at x.

For necessity, suppose that G⁰ contains an odd cycle C2r+1. When attempting to decompose G⁰ + {x}, 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 G⁰ + {x}. Now suppose that G⁰ contains a path P2s. The same argument applies, as P2^s contains an odd number of edges, and any 3-star of G⁰ + {x} contains either zero or two edges of P2s.

Theorem 3.5. 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.

• (i) n ≡ 1 or 2 (mod 3)
• (ii) G⁰ 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 G⁰ has only vertices of degree 0 or 1, and consider a potential decomposition of G⁰ + K² where V (K2) = {x, y}. Any edge e = ab of G⁰ must appear in a 3-star centered at a or b. Removing from G⁰ + K² all such 3-stars centered at vertices of G0, we are left with a graph G¹ in which deg(x) = deg(y) and x, y are the only vertices of degree greater than 2. Consequently, any further 3-stars in G¹ 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(x) ≡ 0 (mod 3). This implies deg(y) − 1 ≡ 0 (mod 3), giving us a contradiction.

For sufficiency of the second condition, let v¹ ∈ V (G0) where deg(v1) = 2. We again consider a staircase diagram of G⁰ and note that the leftmost column has two blank cells. Affix two additional rows to the diagram labeled R¹ and R² where again, r1, r² denote the total number of empty cells in the corresponding row. Define α¹ and α² as is done in the proofs of Theorems 3.1 and 3.2.

Case 1. n ≡ 1 (mod 3)

We have α¹ ≡ α² (mod 3) with r¹ ≡ 1 (mod 3) and r² ≡ 2 (mod 3). As we only have two additional rows, we are forced to place all 2-drops in rows R¹ and R2. If α² ≡ 1 (mod 3), place all 1-drops in row R2. If α² ≡ 2 (mod 3), instead place all 1-drops in row R1. And if α² ≡ 0 (mod 3) (which necessarily implies α² ≥ 3), place one 1-drop in row R¹ and the rest in row R2.

Case 2. n ≡ 2 (mod 3)

Here, α¹ ≡ α² + 1 (mod 3), r¹ ≡ 2 (mod 3), and r² ≡ 0 (mod 3). Again, we are forced to place all 2-drops in rows R¹ and R2. If α² ≡ 1 (mod 3), place all 1-drops in row R2. If instead α² ≡ 2 (mod 3), place all 1-drops in row R1. And if α² ≡ 0 (mod 3) (which again means α² ≥ 3), place one 1-drop in row R¹ and the rest in row R2.

Finally, we note that for any n ≡ 2 (mod 3), there indeed exists a partial 3-star decomposition P of Kⁿ that requires s ≥ 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 G⁰ 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 K⁵

If n ≥ 8, label the vertices of Kⁿ as v1, . . . , vn, and by Theorem 3.3, there exists a 3-star decomposition of the induced subgraph of Kⁿ on vertices v1, . . . , vn−1. We have deg(vn) ≡ 1 (mod 3) so we can remove 3-stars centered at vⁿ until only one edge remains.

References

• [1] A. De Vas Gunasekara and D. Horsley, Smaller embeddings of partial k-star decompositions, arXiv:2109.13475 (2021).
• [2] D.G. Hoffman and D. Roberts, Embedding partial k-star designs, J. Combin. Designs 22 (4) (2013), 161 – 170.
• [3] M. Noble and S.N. Richardson, Balls, bins, and embeddings of partial k-star designs, Discrete Math. 342(12) (2019), Article 111600.
• [4] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979), 273 – 278.
• [5] M. Tarsi, On the decomposition of a graph into stars, Discrete Math. 36 (1981), 299 304.
• [6] S. Yamamoto, H. Ikeda, S. Shige-Ida, K. Ushio, and N. Hamada, On claw-decomposition of complete graphs and complete bigraphs, Hiroshima Math. J. 5 (1975), 33 – 42.