Lambda-fold theta graphs: metamorphosis into 6-cycles (Q2512570)

A \(G\)-design of order \(n\) is an edge-decomposition of the complete graph \(K_n\) into graphs isomorphic to \(G\). Frequently (including here), an additional parameter \(\lambda\) is introduced, and decomposition of the \(\lambda\)-fold complete multigraph is considered. These objects generalize balanced incomplete block designs, so that `blocks' become `copies of \(G\)'. Here we consider decomposition into simple undirected graphs only, although multiple edges, loops, and directions lead to natural questions. As with the block design case, there are `divisibility' restrictions on \(n\) given \(G\) and \(\lambda\). We must have \(\lambda \binom{n}{2}\) divisible by the number of edges of \(G\), and, moreover, \(\lambda(n-1)\) divisible by the greatest common divisor of the degrees in \(G\). Suppose \(H\) is a subgraph of \(G\) and \(\lambda,n\) satisfy the above divisibility requirements for both \(G\) and \(H\). A metamorphosis from a \(\lambda\)-fold \(G\)-design of order \(n\) into a \(\lambda\)-fold \(H\)-design of order \(n\) is obtained by selecting subgraphs isomorphic to \(H\) from the \(G\)-blocks, and then decomposing the remaining edges into further copies of \(H\). Metamorphosis of graph designs is natural for embedding questions, and has received recent attention in its own right for various small graphs \(G\) and \(H\). This article considers metamorphosis in the case when \(H=C_6\), the six-cycle, and \(G\) is the theta graph \(\Theta(1,3,3)\) consisting of a six-cycle with a `diagonal chord'. The crux of the metamorphosis question, then, is that these chords must arrange into copies of \(C_6\). Table 1 in this paper gives a nice summary of the divisibility conditions. The main result of the article is that these divisibility conditions are sufficient. The proof technique is to exhibit various explicit examples (including decompositions of certain complete bipartite graphs) and then to combine these with standard recursive constructions. The presentation is concise and nicely written.