Completely Transitive Codes in Hamming Graphs

AbstractA code in a graph Γ is a non-empty subset C of the vertex set V of Γ. Given C, the partition of V according to the distance of the vertices away from C is called the distance partition of C. A completely regular code is a code whose distance partition has a certain regularity property. A special class of completely regular codes are the completely transitive codes. These are completely regular codes such that the cells of the distance partition are orbits of some group of automorphisms of the graph. This paper looks at these codes in the Hamming Graphs and provides a structure theorem which shows that completely transitive codes are made up of either transitive or nearly complete, completely transitive codes. The results of this paper suggest that particular attention should be paid to those completely transitive codes of transitive type