Fully automorphic decompositions of graphs
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.
This page was built for publication: Fully automorphic decompositions of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2839731)
