Premium
Block diagonalization of adjacency and Laplacian matrices for graph product; applications in structural mechanics
Author(s) -
Kaveh A.,
Rahami H.
Publication year - 2006
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.1696
Subject(s) - adjacency matrix , cartesian product , eigenvalues and eigenvectors , adjacency list , lexicographical order , laplacian matrix , graph product , cartesian coordinate system , mathematics , graph , laplace operator , graph energy , computer science , combinatorics , geometry , graph power , line graph , mathematical analysis , physics , pathwidth , quantum 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.