On decompositions of complete graphs into unicyclic disconnected bipartite graphs on nine edges

Alan Bonhert, Luke Branson, Patrick Joseph Otto

Abstract


We use Rosa-type labelings to decompose complete graphs into unicyclic, disconnected, bipartite graphs on nine edges – namely, those featuring cyclic component C4, C6, or C8. For any such graph H, we prove there exists an H-design of K18k + 1 and K18k for all positive integers k.

Keywords


Rosa-type labelings; graph decompositions; unicyclic graphs

Full Text:

PDF

References

G. Aspenson, D. Baker, C. Schwieder, Decomposing K18n and K18n + 1 into isomorphic, connected, unicyclic 9-edge graphs, Electron. J. Graph Theory Appl. 11 (1) (2023), 275–318.

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

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

S.I. El-Zanati, C. Vanden Eynden, On Rosa-Type Labelings and Cyclic Graph Decompositions, Math. Slovaca 59 (2009), 1–18.

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.

D. Froncek, M. Kubesa, Decomposition of complete graphs into connected unicyclic bipartite graphs with seven edges, Bull. Inst. Combin. Appl. 93 (2021), 52–80

D.X. Li, Isomorphic decomposition of complete graphs into graceful forests, J. Math. Res. Exposition 12 (1992), no. 4, 612–616.

C. Huang, A. Rosa, Decomposition of complete graphs into trees, Ars Combin. 5 (1978), 23–63.

A. Rosa, On certain valuations of the vertices of a graph. Theory of Graphs: Internat. Sympos., Rome, 1966 (P. Rosenstiehl, ed.), Dunod/Gordon and Breach, Paris/New York, 1967, 349–355.

S. Ruiz, Isomorphic decomposition of complete graphs into linear forests, J. Graph Theory 9 (1985), no. 1, 189–191.


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