Uniformly resolvable decompositions of K v K_{v} into 1 1 -factors and odd n n -star factors
Jehyun Lee, Melissa Keranen · 2025
Read Uniformly resolvable decompositions of K v K_{v} into 1 1 -factors and odd n n -star factors by Jehyun Lee, Melissa Keranen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15148.txt.
Introduction
Jehyun Lee and Melissa Keranen study ways to split a complete graph into uniform layers of small pieces. Their 2025 note treats uniformly resolvable decompositions, where the edges of the graph are grouped into classes and each class holds copies of one shape. Two shapes are in play: single edges and stars with an odd number of spokes. The authors give a partial solution for the mixed case, narrowing an open question in design theory.
Catalog record
| CREATOR | Jehyun Lee, Melissa Keranen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15148
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Uniformly resolvable decompositions of K v K_{v} into 1 1 -factors and odd n n -star factors Jehyun Lee, Melissa Keranen Abstract We consider uniformly resolvable decompositions of K v K_{v} into subgraphs such that each resolution class contains only blocks isomorphic to the same graph. We give a partial solution for the case in which all resolution classes are either K 2 K_{2} or K 1 , n K_{1,n} where n n is odd. 1 Introduction Let G=(V,E) be a graph. An {\cal H} - decomposition of the graph G is a collection of edge disjoint subgraphs {\cal H}=\{H_{1},H_{2},\dots,H_{a}\} such that every edge of G appears in exactly one graph H_{i}\in{\cal H} . The subgraphs, H_{i}\in{\cal H} , are called blocks. An {\cal H} -decomposition is called resolvable if the blocks in {\cal H} can be partitioned into classes (or factors) F_{i} , such that each F_{i} is a spanning subgraph of G . A resolvable {\cal H} -decomposition is also called an {\cal H} -factorization of G , and its classes are referred to as {\cal H} -factors. An {\cal H} -decomposition is called uniformly resolvable if each factor F_{i} consists of blocks that are all isomorphic. In the case of uniformly resolvable \mathcal{H} -decompositions, existence results can be categorized based on \mathcal{H} : when {\cal H} is a set of two complete graphs of order at most five in [ 7 , 23 , 25 , 26 ] ; when {\cal H} is a set of two or three paths on two, three or four vertices in [ 10 , 11 , 19 ] ; for {\cal H}=\{P_{3},K_{3}+e\} in [ 9 ] ; for {\cal H}=\{K_{3},K_{1,3}\} in [ 14 ] ; for {\cal H}=\{C_{4},P_{3}\} in [ 21 ] ; and for {\cal H}=\{K_{3},P_{3}\} in [ 22 ] . If {\cal H}=\{H_{1},H_{2}\} , then we may also consider how many factors contain copies of H_{1} and how many factors contain copies of H_{2} . We let (H_{1},H_{2}) - URD(v;r,s) denote a uniformly resolvable decomposition of K_{v} into r classes containing only copies of H_{1} and s classes containing only copies of H_{2} . In this paper, we consider the existence problem for \{H_{1},H_{2}\}=\{K_{2},K_{1,n}\} . While the general case (K_{2},K_{1,n}) - URD(v;r,s) is still open and in progression, we have observed that the standard methods used for most cases of (r,s) are not applicable to solve the cases when number of 1 -factors is small. Thus, we studied these cases separately. With regards to the extremal cases, we have the following. A K_{2} -factorization of G is known as a 1 - factorization and its factors are called 1- factors . We let I denote a 1 -factor. It is well known that a 1-factorization of K_{v} exists if and only if v is even ( [ 20 ] ). If n=3 , that is, the case of (K_{2},K_{1,3}) - URD(v;r,s) , necessary and sufficient conditions for the existence of the decomposition was given in [ 5 ] . If n=4 , that is, the case of (K_{2},K_{1,4}) - URD(v;r,s) , necessary and sufficient conditions for the existence of the decomposition was given in [ 12 ] . If n=5 , that is, the case of (K_{2},K_{1,5}) - URD(v;1,s) , necessary and sufficient conditions for the existence of the decomposition was given in [ 16 ] . A generalization of this to the case of (K_{2},K_{1,n}) - URD(v;1,s) for odd n\geq 3 is also completely solved in [ 17 ] . In this paper, we focus on the (K_{2},K_{1,n}) - URD(v;r,s) for all (r,s) pairs where r,s\geq 1 , and we give a partial solution to the existence problem of a (K_{2},K_{1,n}) -URD (v; r,s) . 2 Necessary Conditions Lemma 2.1 . Let n\geq 3 be an odd integer. If a (K_{2},K_{1,n})-URD(v;r,s) exists, then there is an integer x , 0\leq x\leq\lfloor\frac{v-1}{2n}\rfloor , such that s=(n+1)x and r=v-1-2nx . Further, v\equiv 0\pmod{2} if r>0 and v\equiv 0\pmod{(n+1)} if s>0 . Proof. Assume that there exists a (K_{2},K_{1,n})-URD(v;r,s). By counting the number of edges of K_{v} that appear in the factors it follows that \displaystyle r\frac{v}{2}+s\frac{nv}{n+1}=\frac{v(v-1)}{2}, and hence \displaystyle(n+1)r+2ns=(n+1)(v-1). (1) Let S be the set of s K_{1,n} -factors, and let R be the set of r 1-factors. Because the factors of R are regular of degree 1, every vertex of K_{v} is incident to r edges in R and (v-1)-r edges in S . Assume that any fixed vertex appears in x factors of S with degree n and in y factors of S with degree 1. Because \displaystyle x+y=s\textrm{ and }nx+y=v-1-r, equation ( 1 ) gives \displaystyle(n+1)(v-1-nx-y)+2n(x+y)=(n+1)(v-1). This implies y=nx and s=(n+1)x . Further, replacing s=(n+1)x in Equation (1) provides r=v-1-2nx , where x\leq\frac{v-1}{2n} (because r is a non-negative integer). Finally, if r>0 , then v must be even; while if s>0 , then necessarily n+1 divides v (because K_{1,n} is a graph on n+1 vertices). ∎ If there exists a (K_{2},K_{1,n})-URD(v;r,s) with s=0 , the result is a 1 -factorization(see [ 20 ] ). So, we will consider the cases with s>0 . Therefore, v\equiv 0\pmod{n+1} , and we will prove the existence of a (K_{2},K_{1,n}) - URD(v;r,s) for all possible (r,s)\in\mathcal{J}=\{(r,s)|r=v-1-2nx,s=(n+1)x,\textrm{ with }0\leq x\leq\lfloor\frac{v-1}{2n}\rfloor\} . 3 Weighted Graphs and Preliminary Results Let G be a graph, and t be a positive integer. A weighted graph G_{(t)} is a graph on V(G)\times\mathbb{Z}_{t} with edge set \{\{x_{i},y_{j}\}:\{x,y\}\in E(G),i,j\in\mathbb{Z}_{t}\} . We refer to the construction of G_{(t)} from G as “giving weight t to G ” . For some positive integer m , let K_{m} be a complete graph. Then, for some positive integer n , let K_{m(n+1)} be the graph obtained by giving weight n+1 to K_{m} . Then for each x\in V(K_{m}) , let K_{n+1}^{x} denote a complete graph with vertex set V(K_{n+1}^{x})=\{x_{i}|x\in K_{m},i\in\mathbb{Z}_{n+1}\} . Note that each K_{n+1}^{x} are mutually disjoint. Thus, for v=m(n+1) , we can view the complete graph K_{v} as K_{v}=K_{m(n+1)}\cup\Big(\bigcup\limits_{x\in V(K_{m})}K_{n+1}^{x}\Big) . For our purposes, we will decompose K_{m(n+1)} into weighted cycles C_{m(n+1)} . We begin with two well-known results about the decomposition of complete graphs into cycles. Lemma 3.1 . (Alspach, Brian (2001)) : For positive odd integers m and n with 3\leq m\leq n , the graph K_{n} can be decomposed into cycles of length m if and only if the number of edges in K_{n} is a multiple of m . Lemma 3.2 . (Alspach, Brian (2001)) : For positive even integers m and n with 4\leq m\leq n , the graph K_{n}-I can be decomposed into cycles of length m if and only if the number of edges in K_{n}-I is a multiple of m . It is obvious that m divides |E(K_{m})| , thus if m is odd, by Lemma 3.1 we can decompose K_{m} into m -cycles. The number of m -cycles in the decomposition is: \displaystyle|E(K_{m})|=\frac{m(m-1)}{2}\cdot\frac{1}{m}=\frac{m-1}{2}. Similarly if m is even, by Lemma 3.2 , we can decompose K_{m} into I and \frac{m-2}{2} m -cycles. Now give weight n+1 to K_{m} and to each m -cycle, C_{m} to obtain K_{m(n+1)} and copies of weighted m -cycle, C_{m(n+1)} . An m -cycle and a weighted m -cycle is illustrated in Figure 1 . Hence, we have