Decomposition of K_{18n} and K_{18n+1} into Isomorphic Unicyclic Tripartite 9-Edge Graphs Containing a 3-Cycle with Trees Extending From One Vertex
An H-decomposition of a graph G is a collection of graphs H_1,H_2,···,H_m, all isomorphic to H, such that every edge of G belongs to exactly one H_i for 1 ≤ i ≤ m. A unicyclic graph is a graph containing exactly one cycle, and a k-cycle is a cycle of length k. Thus, a 3-cycle is a cycle of length three. The problem of H-decompositions of complete graphs into isomorphic H_i is largely solved for graphs H with up to eight edges. Thus, we show that for any connected graph H with nine edges and containing exactly one 3-cycle, the graph H decomposes K_{18n} and K_{18n+1}.The constructions are based on Rosa-type labelings, especially ρ-tripartite and 1-rotational ρ-tripartite labelings, which will also be discussed. Keywords: Rosa-type labeling, graph decomposition, tripartite graphs