DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

B. Freyberg

Bryan Freyberg

University of Minnesota Duluth

email: frey0031@d.umn.edu

0000-0001-8246-5896

R. Peters

Ryan Peters

University of Minnesota Duluth

email: pet04060@d.umn.edu

Title:

Decomposition of complete graphs into forests with six edges

PDF

Source:

Discussiones Mathematicae Graph Theory 45(2) (2025) 677-706

Received: 2024-02-22 , Revised: 2024-06-06 , Accepted: 2024-06-07 , Available online: 2024-07-18 , https://doi.org/10.7151/dmgt.2554

Abstract:

Let $G$ be a forest with six edges. We prove that $G$ decomposes the complete graph $K_n$ if and only if $n \equiv 0,1,4, \; \text{or} \; 9 \pmod{12},$ unless $n=9$ and $G$ is one of nine exceptional forests.

Keywords:

graph decomposition, forests, $\rho$-labeling

References:

  1. J. Ahern, B. Freyberg, D. Froncek and M. Keranen, Decompositions of complete graphs into disconnected unicyclic graphs with six edges (2024), manuscript.
  2. J.C. Bermond, Cycles dans les graphes et $G$-configurations, PhD Thesis, University of Paris XI (Orsay, 1975).
  3. J.C. Bermond, C. Huang, A. Rosa and D. Sotteau, Decomposition of complete graphs into isomorphic subgraphs with five vertices, Ars Combin. 10 (1980) 211–254.
  4. J.C. Bermond and J. Schönheim, $G$-decomposition of $K_n$, where $G$ has four vertices or less, Discrete Math. 19 (1977) 113–120.
    https://doi.org/10.1016/0012-365X(77)90027-9
  5. P. Cain, Decomposition of complete graphs into stars, Bull. Aust. Math. Soc. 10 (1974) 23–30.
    https://doi.org/10.1017/S0004972700040582
  6. D. de Werra, On some combinatorial problems arising in scheduling, Canad. Operational Res. Soc. J. 8 (1970) 165–175.
  7. S.I. El-Zanati and C. Vanden Eynden, On Rosa-type labelings and cyclic graph decompositions, Math. Slovaca 59 (2009) 1–18.
    https://doi.org/10.2478/s12175-008-0108-x
  8. B. Freyberg and N. Tran, Decomposition of complete graphs into bipartite unicyclic graphs with eight edges, J. Combin. Math. Combin. Comput. 114 (2020) 133–142.
  9. D. Froncek and B. Kubesa, Decomposition of complete graphs into connected unicyclic bipartite graphs with seven edges, Bull. Inst. Combin. Appl. 93 (2021) 52–80.
  10. D. Froncek and A. Sailstad, Decompositions of complete graphs into forests with five edges (2024), manuscript.
  11. H. Hanani, The existence and construction of balanced incomplete block designs, Ann. Math. Statist. 32 (1961) 361–386.
    https://doi.org/10.1214/aoms/1177705047
  12. C. Huang and A. Rosa, Decomposition of complete graphs into trees, Ars Combin. 5 (1978) 23–63.
  13. Q. Kang and Z. Wang, Optimal packings and coverings of $\lambda K_{v}$ with graphs $K_{5}-P_{5}$, Bull. Inst. Combin. Appl. 41 (2004) 22–41.
  14. T.P. Kirkman, On a problem in combinations, Cambridge Dublin Math. J. 2 (1847) 191–204.
  15. A. Kotzig, Decomposition of a complete graph into $4k$-gons, Mat. Čas. 15 (1965) 229–233, in Russian.
  16. M. Meszka, (2024), personal communication.
  17. A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs, International Symp. Rome 1966, (Dunod Gordon and Breach, Science Publishers, Inc. New York and Dunod Paris 1967) 349–355.
  18. S. Yamamoto, H. Ikeda, S. Shige-eda, K. Ushio and N. Hamada, On claw-decomposition of complete graphs and complete bigraphs, Hiroshima Math. J. 5 (1975) 33–42.
  19. J. Yin and B. Gong, Existence of $G$-designs with $|V(G)|=6$, in: Combinatorial Designs and Applications, W.D. Wallis et al. (Ed(s)), (Marcel Dekker, New York 1990) 201–218.
Close