Dustin Baker

An H-decomposition of a graph G is a collection of subgraphs of G all isomorphic to H such that every edge of G belongs to exactly one such subgraph. A unicyclic graph is a graph containing exactly one cycle. We find all decompositions of Kn, where n is congruent to 0 or 1 modulo 18 into connected unicyclic graphs with 9 edges. Research was split into several cases; this task will focus on decompositions into graphs with an odd cycle of length at least 5. Decompositions were obtained using rho-tripartite labeling and 1-rotational rho-tripartite labeling. Keywords: Graph decomposition, nine edges, rho-tripartite labeling, 1-rotational rho-tripartite labeling