Fully automorphic decompositions of graphs (Q2839731)

A decompositon \({\mathcal D}\) of a graph \(H\) by a graph \(G\) is a partition of \(E(H)\) such that the subgraph induced by the edges in each class of the partition is isomorphic to \(G\). The intersection graph \(I({\mathcal D})\) of \({\mathcal D}\) has a vertex for each class of the partition and two classes are adjacent if and only if they have a common vertex in \(H\). If \(I({\mathcal D})\) is isomorphic to \(H\), then \({\mathcal D}\) is said to be an automorphic decomposition of \(H\). If the order of \(G\) equals the chromatic number of \(H\) as well, then \({\mathcal D}\) is said to be a fully automorphic decomposition. In this paper several necessary conditions for the existence of a fully automorphic decomposition are proposed and the question of whether a fully automorphic host \(H\) will have an even degree of regularity is studied. An infinite class of fully automorphic decompositions using circulants and valuations is given.