Fully Automorphic Decompositions of Graphs

Abstract

A decomposition $\mathcal{D}$ of a graph $H$ by a graph $G$ is a partition of the edge set of $H$ such that the subgraph induced by the edges in each part of the partition is isomorphic to $G$. The intersection graph $I(\mathcal{D})$ of the decomposition $\mathcal{D}$ has a vertex for each part of the partition and two parts $A$ and $B$ are adjacent if and only if they share a common node in $H$. If $I(\mathcal{D})\cong H$, then $\mathcal{D}$ is an automorphic decomposition of $H$. If $n(G)=\chi (H)$ as well, then we say that $\mathcal{D}$ is a fully automorphic decomposition. In this paper, we examine the question of whether a fully automorphic host will have an even degree of regularity. We also give several examples of fully automorphic decompositions as well as necessary conditions for their existence.