Decomposition of complete graphs into forests with six edges (Q6985847)

In this paper, the authors settle the problem of determining the decomposition spectrum of the complete graph \(K_n\) by all forests with exactly six edges. By definition for some graph \(G\), a \(G\)-decomposition of a graph \(H\) is a set \(\mathcal{G}\) \(=\) \(\{G_1, G_2, \dots, G_t \}\) of pairwise edge-disjoint subgraphs of \(H\), each of which is isomorphic to \(G\), such that \(E(H) = \bigcup^{t}_{i=1}E(G_i)\). Building on classical results in graph labelings and design theory, they establish that a six-edge forest \(G\) admits a \(G\)-decomposition of \(K_n\) if and only if \(n\equiv0,1,4,\) or \(9\pmod{12}\), with precisely nine exceptional forests obstructing the case \(n=9\). By unifying a variety of combinatorial constructions -- Rosa's cyclic edge-length labelings, \(\sigma^{+-}\)-labelings for bipartite graphs, and new modular ``clicking'' operations -- the authors complete the classification for all graphs on at most six edges.\N\NThe first section surveys known decomposition spectra for graphs with up to five edges, and then introduces a consistent notation \(G(k; e_1, e_2, \dots, e_k)_t\) to catalogue forests by their component sizes. The necessary congruence condition \(6 | \binom{n}{2}\) is shown to reduce to \(n\equiv0,1,4,9\pmod{12}\), and Theorem 1 isolates the nine minimal counterexamples at \(n=9\). This overview is both comprehensive and well-referenced, ensuring the reader can place the present work within the broader literature.\N\NThe main theorem is Theorem 1: Let \(G\) be a forest with exactly six edges. There exists a \(G\)-decomposition of \(K_n\) if and only if \(n > 4\) and \(n \equiv 0,1,4\), or 9 (mod 12), unless \(n = 9\) and \(G\) is one of the nine following exceptional forests: \(K_{1,5} \cup K_2\); \(K_{1,4} \cup 2K_2\); \(K_{1,4} \cup P_3\); \(K_{1,3} \cup 3K_2\); \(P_4 \cup 3K_2\); \(2P_3 \cup 2K_2\); \(P_3 \cup 4K_2\); \(6K_2\); \(2K_{1,3}\).\N\NIn Section 2, the authors give a complete characterization of those six-edge forests that fail to decompose \(K_9\). Lemma 2 employs elementary degree-counting arguments -- via the pigeonhole principle -- to eliminate star-forest cases, while known negative results in the literature cover the remaining configurations. Theorem 3 then shows that all other forests do decompose \(K_9\), using an elegant double-labeling of edges by ``length'' and a three-colour residue class. By constructing two base blocks and applying cyclic shifts by three, the authors produce six edge-disjoint copies covering all length-colour pairs, thereby demonstrating the power of modular group actions in decomposition problems.\N\NSection 3 extends the constructive approach to those \(n\) satisfying \(n\equiv0\) or \(1\pmod{12}\). Here, the \(\sigma^{+-}\)-labeling framework of \textit{B. Freyberg} and \textit{N. Tran} [J. Comb. Math. Comb. Comput. 114, 133--142 (2020; Zbl 1459.05258)] is invoked: vertices of a bipartite forest \(G\) with \(m\) edges are assigned labels in \(\{0,\dots,2m-2\}\) so that induced edge-lengths run bijectively through \(\{1,\dots,m\}\) and a distinguished ``long'' edge becomes pendant. Theorem 4 then guarantees \(G\)-decompositions of every \(K_{2mx}\) and \(K_{2mx+1}\) for every positive integer \(x\) when one condition holds: \(G\) is a bipartite graph with \(m\) edges and a \(\sigma^{+-}\)-labeling such that the edge of length \(m\) is a pendant edge \(e\). The authors supply explicit \(\sigma^{+-}\)-labelings for all non-matching six-edge forests, thereby covering the infinite families \(n=12k\) and \(n=12k+1\).\N\NSection 4 addresses the remaining classes \(n\equiv 4\) or \(9\pmod{12}\) with \(n>9\). For odd \(n\), wrap-around edges and a cyclic length function mirroring the \(K_9\) case is defined; for even \(n\), an auxiliary vertex \(\infty\) introduces an ``infinite'' length. Theorems 6 and 7 present starter blocks \(G_1,\dots,G_{k+2}\) (or \(G_1,\dots,G_{k+1}\)) and demonstrate that successive cyclic ``clicking'' by 3 or 1 yields \(n\) blocks of each required length. The uniformity of length counts, the absence of prohibited wrap-around edges in initial blocks, and careful modular index considerations ensure edge-disjointness and completeness.\N\NThe paper concludes by assembling these four theorems to produce Theorem 1, thereby closing the decomposition spectrum for all forests of size six. The work is remarkably thorough: each exceptional case is identified and ruled out, and each infinite family is handled by a clear, reproducible construction. Figures and block diagrams, while numerous, are indispensable for verifying the labelings.\N\NOverall, this paper represents a significant advance in graph decomposition theory, a classic combinatorial problem that was given new life in the 1960s by \textit{A. Kotzig} [Mat.-Fyz. Čas., Slovensk. Akad. Vied 15, 229--232 (1965; Zbl 0134.43402)] and \textit{A. Rosa} [in: Theory Graphs, Int. Symp. Rome 1966, 349--355 (1967; Zbl 0193.53204)] and spans many related fields of graph theory, design theory, and error-correcting codes. Its blend of classical labeling techniques and novel modular constructions not only resolves a natural combinatorial question but also enriches the toolkit available for future design-theoretic investigations.