Fully Automorphic Decompositions of Graphs

Document Type


Publication Date



A decomposition 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(D) of the decomposition D has a vertex for each part of the partition and two parts A and B are adjacent iff they share a common node in H. If I(D) ≅ H, then D is an automorphic decomposition of H. If n(G) = x(H) as well, then we say that 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.

This document is currently not available here.