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 G formed by Cartesian graph products. This process of identification is called the factorization of G and the generators are also known as the factors of G. 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 G, the eigenvalues and eigenvectors of G can easily be determined. The efficiency of the present method is illustrated through six examples of different configurations. (C) 2009 Elsevier B.V. All rights reserved.