Search

Nowadays, graph theory is one of the most exciting fields of mathematics due to the tremendous developments in modern technology, where it is used in many important applications. The orthogonal double cover (ODC) is a branch of graph theory and is considered as a special class of graph decomposition. In this paper, we decompose the complete bipartite graphs Kx,x by caterpillar graphs using the method of ODCs. The article also deals with constructing the ODCs of Kx,x by general symmetric starter vectors of caterpillar graphs such as stars–caterpillar, the disjoint copies of cycles–caterpillars, complete bipartite caterpillar graphs, and the disjoint copies of caterpillar paths. We decompose the complete bipartite graph by the complete bipartite subgraphs and by the disjoint copies of complete bipartite subgraphs using general symmetric starter vectors. The advantage of some of these new results is that they enable us to decompose the giant networks into large groups of small networks with the comprehensive coverage of all parts of the giant network by using the disjoint copies of symmetric starter subgraphs. The use case of applying the described theory for various applications is considered.

Recent developments in commutative algebra, linear algebra, and graph theory allow us to approach various issues in several fields. Circulant graphs now have a wider range of practical uses, including as the foundation for optical networks, discrete cellular neural networks, small-world networks, models of chemical reactions, supercomputing and multiprocessor systems. Herein, we are concerned with the decompositions of the bipartite circulant graphs. We propose the Cartesian and tensor product approaches as helping tools for the decompositions. The proposed approaches enable us to decompose the bipartite circulant graphs into many categories of graphs. We consider the use cases of applying the described theory of bipartite circulant graph decomposition to the problems of finding new topologies and deadlock-free routing in them when building supercomputers and networks-on-chip.