Decomposing K18n and K18n + 1 into connected unicyclic graphs with 9 edges

Grace Aspenson, Dustin Baker, Bryan Freyberg, Coy Schwieder

Abstract


Other than C9 there are 239 connected unicyclic graphs with exactly 9 edges. We use established graph labeling results to prove that every one of them decomposes the complete graph Kn if n ≡ 0 or 1 (mod 18).

Keywords


Graph decomposition, ρ-labeling

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2023.11.1.22

References

A. Bohnert, L. Branson, P. Otto, On decompositions of complete graphs into unicyclic disconnected graphs on nine edges, Electron. J. Graph Theory Appl. 11 (1) (2023), 331–343.

A. Rosa, On certain valuations of the vertices of a graph, In: Theory of Graphs (Intl. Symp. Rome 1966), Gordon and Breach, Dunod, Paris, 1967, 349–355.

B. Alspach, H. Gavlas, Cycle Decompositions of Kn and Kn − I, J. Combin. Theory, Ser. B 81 (2001), 77–99.

B. Freyberg, D. Froncek, Decomposition of complete graphs into unicyclic graphs with eight edges, J. Combin. Math. Combin. Comput. 114 (2020), 113–132.

B. Freyberg, N. Tran, Decomposition of complete graphs into bipartite unicyclic graphs with eight edges, J. Combin. Math. Combin. Comput. 114 (2020), 133–142.

D. Froncek, B. Kubik, Decomposition of complete graphs into tricyclic graphs with eight edges, J. Combin. Math. Combin. Comput. 114 (2020), 143–166.

D. Froncek, J. Lee, Decomposition of complete graphs into bicyclic graphs with eight edges, Bull. Inst. Combin. Appl. 88 (2020), 30–49.

D. Froncek, M. Kubesa, Decomposition of complete graphs into connected unicyclic bipartite graphs with seven edges, Bull. Inst. Combin. Appl., accepted.

D. Froncek, O. Kingston, Decomposition of complete graphs into connected unicyclic graphs with eight edges and pentagon, Indonesian J. Combin. 3 (1) (2019), 24–33.

J. Fahnenstiel, D. Froncek, Decomposition of complete graphs into connected unicyclic bipartite graphs with eight edges, Electron. J. Graph Theory Appl. 7 (2) (2019), 235–250.

R. Bunge, On 1-Rotational decompositions of complete graphs into tripartite graphs, Opuscula Math. 39 (5) (2019), 623–643.

R. Bunge, A. Chantasartrassmee, S. I. El-Zanati, and C. Vanden Eynden, On cyclic decompositions of complete graphs into tripartite graphs, J. Graph Theory 72 (2013), 90–111.

S. I. El-Zanati, C. Vanden Eynden, On Rosa-type labelings and cyclic graph decompositions, Math. Slovaca 59 (2009), 1–18.

S. I. El-Zanati, C. Vanden Eynden, On the cyclic decomposition of complete graphs into bipartite graphs, Australas. J. Combin. 24 (2001), 209–219.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats