Factorization for efficient solution of eigenproblems of adjacency and Laplacian matrices for graph products

Many structural models can be generated as the graph products of two or three subgraphs known as their generators. The main types of graph products consist of Cartesian, strong Cartesian, direct, and lexicographic products. In this paper, a general method is presented for the factorization of these graph products, such that the eigenvalues of the entire graph are obtained as the union of the eigenvalues of the weighted subgraphs defined here. The adjacency and Laplacian matrices for each graph product are studied separately. For graphs with missing elements (cut-outs), the eigenvalues are calculated with the additional use of the Rayleigh quotient approach. The main idea stems from the rules recently developed by the authors for block diagonalization of matrices. These products have many applications in computational mechanics, such as ordering, graph partitioning, dynamic analysis, and stability analysis of structures. Some of these applications are addressed in this paper. Copyright (C) 2007 John Wiley & Sons, Ltd.