A unified method for eigendecomposition of graph products. (English) Zbl 1066.05087

Summary: A unified method is developed for calculating the eigenvalues of the weighted adjacency and Laplacian matrices of three different graph products. These products have many applications in computational mechanics, such as ordering, graph partitioning, and subdomaining of finite element models.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
Full Text: DOI


[1] Kaveh, Structural Mechanics: Graph and Matrix Methods (2004)
[2] Kaveh, Optimal Structural Analysis (2005)
[3] Biggs, Algebraic Graph Theory (1993) · Zbl 0284.05101
[4] Cvetković, Spectra of Graphs, Theory and Applications (1980)
[5] Godsil, Algebraic Graph Theory (2001)
[6] Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal 23 pp 298– (1973) · Zbl 0265.05119
[7] Mohar, Graph Theory, Combinatorics and Applications 2 pp 871– (1991)
[8] Pothen, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications 11 pp 430– (1990) · Zbl 0711.65034
[9] Topping BHV Sziveri J Parallel subdomain generation method 1995
[10] Kaveh, A new spectral method for nodal ordering of regular space structures, Finite Elements in Analysis and Design 40 (13/14) pp 1931– (2004)
[11] Kaveh, An efficient method for decomposition of regular structures using graph products, International Journal for Numerical Methods in Engineering 61 pp 1797– (2004) · Zbl 1075.74539
[12] Gould, The geographical interpretation of eigenvalues, Transactions of the Institute of British Geographer 42 pp 53– (1967)
[13] Grimes, A new algorithm for finding a pseudo-peripheral node in a graph, SIAM Journal on Analysis and Applications 11 pp 323– (1990)
[14] Kaveh, Algebraic and topological graph theory for ordering, Zeitschrift Angewandte Mathematik und Mechanik 71 pp T739– (1991) · Zbl 0765.05069
[15] Paulino, Node and element resequencing using Laplacian of a finite element graph. Part-I-general concepts and algorithms, International Journal for Numerical Methods in Engineering 37 pp 1511– (1994)
[16] Simon, Partitioning of unstructured problems for parallel processing, Computing in System Engineering 2 pp 135– (1991)
[17] Seale C Topping BHV Parallel implementation of recursive spectral bisection 1995 459 473
[18] Kaveh, Spectral bisection of adaptive finite element meshes for parallel processing, Computers and Structures 70 pp 315– (1999) · Zbl 0969.74594
[19] Kaveh, Spectral trisection of finite element models, computers and structures, International Journal of Numerical Methods for Heat and Fluid Flow 11 pp 358– (2001) · Zbl 0977.74060
[20] Kaveh, A multi-level finite element nodal ordering using algebraic graph theory, Finite Elements in Analysis and Design 38 pp 245– (2002)
[21] Sabidussi, Graph multiplication, Mathematische Zeitschrift 72 pp 446– (1960) · Zbl 0093.37603
[22] Weichsel, The Kronecker product of graphs, Proceedings of the American Mathematical Society 13 pp 47– (1962) · Zbl 0102.38801
[23] Kaveh A Rahami H New canonical forms for analytical solution of problems in structural mechanics 2005 · Zbl 1330.74105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.