Fully automorphic decompositions of graphs
type: Item
instance of: scholarly article
zbMATH Open document ID: 1271.05076
author: Robert A. Beeler
publication date: 2013-07-12T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C51
zbMATH DE Number: 6187631
zbMATH Keywords: fully automorphic decomposition
zbMATH Keywords: intersection graph
zbMATH Keywords: chromatic number
zbMATH Keywords: independence number
zbMATH Keywords: regular graph
zbMATH Keywords: circulant
zbMATH Keywords: valuation
zbMATH Keywords: graceful tree
MaRDI profile type: Publication
title: Fully automorphic decompositions of graphs
published in: JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing
review text: 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.
reviewed by: Ioan Tomescu
description: scientific article; zbMATH DE number 6187631