Block diagonalization of adjacency and Laplacian matrices for graph product; applications in structural mechanics

Eigenvalues and eigenvectors of graphs have many applications in structural mechanics and combinatorial optimization. For a regular space structure, the visualization of its graph model as the product of two simple graphs results in a substantial simplification in the solution of the corresponding eigenproblems. In this paper, the adjacency and Laplacian matrices of four graph products, namely, Cartesian, strong Cartesian, direct and lexicographic products are diagonalized and efficient methods are obtained for calculating their eigenvalues and eigenvectors. An exceptionally efficient method is developed for the eigensolution of the Laplacian matrices of strong Cartesian and direct products. Special attention is paid to the lexicographic product, which is not studied in the past as extensively as the other three graph products. Examples are provided to illustrate some applications of the methods in structural mechanics. Copyright 2006 John Wiley & Sons, Ltd