3-Cycle Systems and Structure within Graph Decompositions

Abstract

An $H$-decomposition of a graph $G$ is a partition of the edge set $E(G)$ such that each element of the partition induces a subgraph isomorphic to $H$. A packing or cover of $\lambda K_n$ (with triples) is an ordered pair $(V,B)$ where $V$ is an $n$-element set and $B$ is a set of $3$-element subsets of $V$ called blocks such that each $2$-element subset of $V$ appears in at most $\lambda$ blocks or at least $\lambda$ blocks respectively. Define $E(B)=\{\{x,y\},\{x,z\},\{y,z\}\mid \{x,y,z\}\in B\}$. The leave of a packing is defined to be the multiset of edges $L=E(\lambda K_n)-E(B)$ and the excess or padding of a cover is defined to be the multiset of edges $P=E(B)-E(\lambda K_n)$.

In this dissertation, necessary and sufficient conditions for the existence of $K_3$- \\ decompositions of $K=\lambda_1 K_m \vee_{\lambda_2} \lambda_1 K_n$ are found when $\lambda_1\geq\lambda_2$, vastly generalizing the results in the literature on $K_3$-decompositions of $K$. In a specific case of this problem (namely when $n=2$), it is useful to know for which simple quadratic subgraphs $Q$ of $K_n$ (so $Q$ cannot have $2$-cycles) do there exist a $K_3$-decomposition of $\lambda K_n-E(Q)$ (that is, a packing of $\lambda K_n$ with leave equal to $E(Q)$). A complete solution to this question is provided; in addition to being useful in proving the first result, it is also significant in that it extends a classic result of Colbourn and Rosa who answered the same question when $\lambda=1$.

In terms of the quadratic leave problem, the previous result, while short and simple, has a gap in that it does not allow $Q$ to have $2$-cycles; the next result resolves this issue. In a packing of $2K_n$, the neighborhood graph of a vertex $v$ is defined to be the graph induced by the multiset of edges $\{\{a,b\}\mid\{a,b,v\}\in B\}$. In a maximum packing of $2K_n$, the neighborhood graph of a vertex is a $2$-regular graph on either $n-1$ or $n-2$ vertices. Colbourn and Rosa provided a chararterization of which $2$-regular graphs on $n-1$ or $n-2$ vertices can be the neighborhood graph of a vertex in some maximum packing of $2K_n$ when $n\equiv 0$ or $1$ (mod $3$); this dissertation provides such a characterization in the case where $n\equiv 2$ (mod $3$). This result along with the Colbourn and Rosa result ($n\equiv 0$ or $1$ (mod $3$)) is used to find necessary and sufficient conditions for a $K_3$-decomposition of $\lambda K_n-E(Q)$ where $Q$ is any $2$-regular graph on at most $n$ vertices (so $Q$ can have $2$-cycles).

Finally, having already found necessary and sufficient conditions for $Q$ to be a $2$-regular leave of $\lambda K_n$, the problem of when a quadratic graph $Q$ has edge set equal to the excess of a cover of $\lambda K_n$ is considered, and necessary and sufficient conditions for a $K_3$-decomposition of $\lambda K_n+E(Q)$ appear in the dissertation.