{"entities":{"Q6985847":{"pageid":21418101,"ns":120,"title":"Item:Q6985847","lastrevid":76323876,"modified":"2026-04-23T16:24:57Z","type":"item","id":"Q6985847","labels":{"en":{"language":"en","value":"Decomposition of complete graphs into forests with six edges"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8038168"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6985847$6E495F69-C592-4636-8172-1A763FABCFCA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5850ac5a0b0dddebe3c9f1bc378f7fe375aa57e5","datavalue":{"value":{"text":"Decomposition of complete graphs into forests with six edges","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6985847$7D03AA41-A3F6-4283-B5BD-38FF3AEA380C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af4403d4165742b733977bc6565500afdacaa72c","datavalue":{"value":"1569.05295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6985847$9299BC33-85F2-42AD-8647-8183260AFC45","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11a70142b0ed0a6e56e8458a7bf02881a0cb402b","datavalue":{"value":"10.7151/DMGT.2554","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6985847$329EA976-46FA-454B-8839-67A55B153BBC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f92d2d041f9b9ead05136ffc1c81b68dff8df521","datavalue":{"value":{"entity-type":"item","numeric-id":1717207,"id":"Q1717207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6985847$8FBD8228-2358-4056-9AAB-A68F96BEAD2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3499276046d7a4a92dbf4437a3a7481e1252a39e","datavalue":{"value":{"entity-type":"item","numeric-id":6985846,"id":"Q6985846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6985847$5FD3D491-380F-4939-B9F1-C30F62A722F9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3269941f6e79d2eeb0f0e3026f28a5ab20f8d53c","datavalue":{"value":{"entity-type":"item","numeric-id":6768872,"id":"Q6768872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6985847$596436DD-FD23-47AD-A0EB-6EA95EC67E7A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b64da13dc72ce934cdd1251103882f41d171d88","datavalue":{"value":{"time":"+2025-05-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6985847$DF0762EF-0575-41EB-9A14-9D6E79DA4124","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ade7012118b1788c68ee0b336d3b4b54a6edd89","datavalue":{"value":"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. \u010cas., 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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6985847$F5CAE65D-DE08-4935-B414-D1F5DB00468A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"48b935df6eb7f96564ed2d571bf624e28f5ba26e","datavalue":{"value":{"entity-type":"item","numeric-id":890869,"id":"Q890869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6985847$8AC4A659-BF95-4241-8AD2-B3C9C6746DB5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6985847$303F4DEF-7C33-478D-81A6-BE896095458C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6985847$B5D76C47-3973-4CBD-8D42-84A832579BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"abea942f78d2e1371fc37b811435f5f387392a55","datavalue":{"value":"05C51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6985847$51F1B699-5E0A-4DB6-81E3-A3426A065E79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c93c8079fb0f8a2d84a4f02889edfad6b6a6d6d8","datavalue":{"value":"8038168","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6985847$D44AECF8-0E1F-4F60-B470-69202B1D748F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cee46e2c6a42a74803d50f6329947494bb4a53f6","datavalue":{"value":"graph decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q6985847$C8C2A0A9-24F5-41DD-BB90-C24E85C822F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab1b2d33963dc85c015ba353e197645da8b8601d","datavalue":{"value":"forests","type":"string"},"datatype":"string"},"type":"statement","id":"Q6985847$1E4A5A88-70A4-48FC-B297-A959EC3B409F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"704fb6cb4de2bb70d60e1eabe52bcb256247890d","datavalue":{"value":"\\(\\rho\\)-labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q6985847$2242D1A9-23B7-492A-97A6-8E5C08E490C5","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6985847$D13AFC43-5B03-4262-8DA8-37449FC01048","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Decomposition of complete graphs into forests with six edges","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Decomposition_of_complete_graphs_into_forests_with_six_edges"}}}}}