Factorization of product graphs for partitioning and domain decomposition

In this paper an efficient algorithm is presented for identifying the generators of regular graph models GG formed by Cartesian graph products. This process of identification is called the factorization of GG and the generators are also known as the factors of GG. Once such a factorization is performed, a simple approach is employed for calculating the second eigenvalues of the factors. Using these eigenvalues, the second eigenvalue of the entire model is obtained and the corresponding eigenvector is employed for bisection of the model. Most of the structural models are regular and can be considered as the product of some simple graphs such as paths and/or cycles. By finding the factors of a given graph GG, the eigenvalues and eigenvectors of GG can easily be determined. The efficiency of the present method is illustrated through six examples of different configurations.