Amalgamations and Detachments of Graphs and Hypergraphs

Abstract

A \textit{detachment} of a graph $H$ is a graph obtained from $H$ by splitting some or all of its vertices into more than one vertex. If $g$ is a function from $V(H)$ into $\mathbb {N}$, then a \textit{$g$-detachment} of $H$ is a detachment of $H$ in which each vertex $u$ of $H$ splits into $g(u)$ vertices. $H$ is an \textit{amalgamation} of $G$ if there exists a function $\phi$ called an \textit{amalgamation function} from $V(G)$ onto $V(H)$ and a bijection $\phi':E(G)\rightarrow E(H)$ such that $e$ joining $u$ and $v$ is in $E(G)$ iff $\phi'(e)$ joining $\phi(u)$ and $\phi(v)$ is in $E(H)$.

We prove that for a given edge-colored graph there exists a detachment so that the result is a graph in which the edges are shared among the vertices in ways that are fair with respect to several notions of balance (such as between pairs of vertices, degrees of vertices in both the graph and in each color class, etc.). The connectivity of color classes is also addressed. Most results in the literature on amalgamations focus on the detachments of amalgamated complete graphs and complete multipartite graphs. Many such results follow as immediate corollaries to the main result, which addresses amalgamations of graphs in general.

We exhibit some applications of this result in Hamiltonian decomposition of several families of graphs, and also we show that many known graph decomposition results can be obtained by a short proof using the main theorem. We study the companion embedding problems with many applications.

We then extend various results by Hilton, Nash-Williams and Rodger to hypergraphs. Such extensions provide a powerful tool to generalizes Baranyai's Theorems, and related results by Berge and Johnson.

We study several hypergraph embedding problems which will extend results of Brouwer, Schrijver, Baranyai, H{\"a}ggkvist and Hellgren.

In connection with Baranyai-Katona conjecture, we provide necessary and sufficient conditions for a complete uniform hypergraph to be connected factorizable, answering a question by Katona.