Metamorphosis Problems for Graph Designs

Abstract

A \(\lambda\)-fold \(G\)-design of order \(n\) is a pair \((X, {B})\), where \(X\) is a set of \(n\) vertices and \({B}\) is a collection of edge-disjoint copies of the simple graph \(G\), called blocks, which partitions the edge set of \(K_n\) (the undirected complete graph with \(n\) vertices) with vertex set \(X\). Let \((X, {B})\) be a \(G\)-design and \(H\) be a subgraph of \(G\). For each block \(B \in \mathcal{B}\), partition \(B\) into copies of \(H\) and \(G \setminus H\) and place the copy of \(H\) in \({B}(H)\) and the edges belonging to the copy of \(G \setminus H\) in \({D}(G \setminus H)\). Now, if the edges belonging to \({D}(G \setminus H)\) can be arranged into a collection \({D}_H\) of copies of \(H\), then \((X, {B}(H) \cup {D}(H))\) is a \(\lambda\)-fold \(H\)-design of order \(n\) and is called a metamorphosis of the \(\lambda\)-fold \(G\)-design \((X, {B})\) into a \(\lambda\)-fold \(H\)-design, denoted by \((G > H) – M_\lambda(n)\).
In this paper, the existence of a \((G > H) – M_\lambda(n)\) for graph designs will be presented, variations of this problem will be explained, and recent developments will be surveyed.