Premium
Factorization for efficient solution of eigenproblems of adjacency and Laplacian matrices for graph products
Author(s) -
Kaveh A.,
Rahami H.
Publication year - 2007
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.2245
Subject(s) - adjacency matrix , eigenvalues and eigenvectors , graph energy , cartesian product , lexicographical order , mathematics , adjacency list , factorization , graph , laplacian matrix , graph product , combinatorics , spectral graph theory , discrete mathematics , voltage graph , line graph , algorithm , physics , pathwidth , quantum mechanics
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 © 2007 John Wiley & Sons, Ltd.