Orthogonal Decompositions of Regular Graphs and Designing Tree-Hamming Codes

Abstract

The paper introduces a concept of graph decomposition. That is orthogonal decompositions. Orthogonal decompositions of a graph H is a partitioning H into subgraphs of H such that  any two subgraphs intersect in at most one edge. This decompositions are called G-orthogonal decompositions of H if and only if every subgraph in such decompositions is isomorphic to the graph G. Such decomposition appear in a lot of applications; statistics, information theory, in the theory of experimental design and many others. An approach of constructing orthogonal decompositions of regular graph is introduced here. Application of this approach for constructing tree -- orthogonal decompositions of complete bipartite graph is considered. Further, the use of orthogonal decompositions for designing hamming tree-codes is also discussed along with examples. The study shows that such codes have an efficient properties when are used to detect and correct the errors that may occur during  a transmission of data through a network. Furthermore, we present a method for the recursive construction of orthogonal decompositions.