On infinite circulant-balanced complete multipartite graphs decompositions based on generalized algorithmic approaches

Abstract

Graph theory is a powerful and essential tool for applied scientists and engineers in analyzing and designing algorithms for several problems. Graph theory has a vital role in complex systems, especially in computer sciences. Applications of graph theory can be found in many scientific disciplines such as operational research, engineering, life sciences, management sciences, coding, and computer science. In the literature, there are two algorithms for constructing decompositions for the circulant graphs C2r,r with 2r vertices and r degree. For r,m⩾2, a circulant-balanced complete multipartite graph Cmr,(m-1)r is a generalization to C2r,r. Here, the major contributions are the generalization of the algorithms used for constructing the decompositions for the circulant graphs C2r,r to generalized algorithms that can be used for the decomposition of Cmr,(m-1)r that have mr vertices and (m-1)r degree. These generalized algorithms manage us to decompose the circulant graphs Cmr,(m-1)r by different graph classes. The paper's novelty is demonstrated by the fact that it is the first to suggest general approaches for decomposing circulant-balanced complete multipartite graphs. The constructed results in the present paper are suitable for generating different codes and also have great importance in the design of experiments.

Keywords

• Multipartite graph
• Decomposition
• Circulant graph
• Graph algorithms
• Infinite graphs