Let \(K_4\backslash e=…\). If we remove the “diagonal” edge, the result is a \(4\)-cycle. Let \((X,B)\) be a \(K_4\backslash e\) design of order \(n\); i.e., an edge-disjoint decomposition of \(K_n\) into copies of \(K_4\backslash e\). Let \(D(B)\) be the collection of “diagonals” removed from the graphs in \(B\) and \(C(B)\) the resulting collection of \(4\)-cycles. If \(C_2(B)\) is a reassembly of these edges into \(4\)-cycles and \(L\) is the collection of edges in \(D(B)\) not used in a \(4\)-cycle of \(C_2(B)\), then \((X, (C_1(B) \cup C_2(B)), L)\) is a packing of \(K_n\) with \(4\)-cycles and is called a metamorphosis of \((X,B)\). We construct, for every \(n = 0\) or \(1\) (mod \(5\)) \(> 6\), \(n \neq 11\), a \(K_4\backslash e\) design of order \(n\) having a metamorphosis into a maximum packing of \(K_n\) with \(4\)-cycles. There exists a maximum packing of \(K_n\) with \(4\)-cycles, but it cannot be obtained from a \(K_4\backslash e\) design.

We investigate the supereulerian graph problems within planar graphs, and we prove that if a \(2\)-edge-connected planar graph \(G\) is at most three edges short of having two edge-disjoint spanning trees, then \(G\) is supereulerian except for a few classes of graphs. This is applied to show the existence of spanning Eulerian subgraphs in planar graphs with small edge cut conditions. We also determine several extremal bounds for planar graphs to be supereulerian.

Given an acyclic digraph \(D\), the phylogeny graph \(P(D)\) is defined to be the undirected graph with \(V(D)\) as its vertex set and with adjacencies as follows: two vertices \(x\) and \(y\) are adjacent if one of the arcs \((x,y)\) or \((y,x)\) is present in \(D\), or if there exists another vertex \(z\) such that the arcs \((x,z)\) and \((y,z)\) are both present in \(D\). Phylogeny graphs were introduced by Roberts and Sheng [6] from an idealized model for reconstructing phylogenetic trees in molecular biology, and are closely related to the widely studied competition graphs. The phylogeny number \(p(G)\) for an undirected graph \(G\) is the least number \(r\) such that there exists an acyclic digraph \(D\) on \(|V(G)| + r\) vertices where \(G\) is an induced subgraph of \(P(D)\). We present an elimination procedure for the phylogeny number analogous to the elimination procedure of Kim and Roberts [2] for the competition number arising in the study of competition graphs. We show that our elimination procedure computes the phylogeny number exactly for so-called “kite-free” graphs. The methods employed also provide a simpler proof of Kim and Roberts’ theorem on the exactness of their elimination procedure for the competition number on kite-free graphs.

A multiple shell \(MS\{n_1^{t_1}, n_2^{t_2}, \dots, n_r^{t_r}\}\) is a graph formed by \(t_i\) shells of widths \(n_i\), \(1 \leq i \leq r\), which have a common apex. This graph has \(\sum_{i=1}^rt_i(n_i-1) + 1\) vertices. A multiple shell is said to be balanced with width \(w\) if it is of the form \(MS\{w^t\}\) or \(MS\{w^t, (w+1)^s\}\). Deb and Limaye have conjectured that all multiple shells are harmonious, and shown that the conjecture is true for the balanced double shells and balanced triple shells. In this paper, the conjecture is proved to be true for the balanced quadruple shells.