×

Block diagonalization of adjacency and Laplacian matrices for graph product; applications in structural mechanics. (English) Zbl 1127.74050

Summary: 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 Laplacian matrices of strong Cartesian and direct products. Special attention is paid to the lexicographic product, which is not studied in the past such extensively as the other three graph products. Examples are provided to illustrate some applications of the methods in structural mechanics.

MSC:

74S30 Other numerical methods in solid mechanics (MSC2010)
74K99 Thin bodies, structures
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Structural Mechanics: Graph and Matrix Methods (3rd edn). Research Studies Press: Somerset, U.K., 2004.
[2] Optimal Structural Analysis (2nd edn). Research Studies Press: Somerset, U.K., 2006. · Zbl 1138.74002 · doi:10.1002/9780470033326
[3] Algebraic Graph Theory (2nd edn). Cambridge University Press: Cambridge, MA, 1993.
[4] , . Spectra of Graphs, Theory and Applications. Academic Press: New York, 1980.
[5] . Algebraic Graph Theory. Springer: New York, 2001. · doi:10.1007/978-1-4613-0163-9
[6] Fiedler, Czechoslovak Mathematical Journal 23 pp 298– (1973)
[7] The Laplacian spectrum of graphs, entitled Graph Theory. In Combinatorics and Applications, et al. (eds), vol. 2. Wiley: New York, 1991; 871–898. · Zbl 0840.05059
[8] Pothen, SIAM Journal on Matrix Analysis and Applications 11 pp 430– (1990)
[9] . Parallel subdomain generation method. In Developments in Computational Techniques for Structural Engineering, Civil-Comp Press, Edinburgh, U.K., 1995.
[10] Kaveh, Communications in Numerical Methods in Engineering 21 pp 377– (2005)
[11] Kaveh, Finite Elements in Analysis and Design 40 pp 1931– (2004)
[12] Kaveh, International Journal for Numerical Methods in Engineering 61 pp 1797– (2004)
[13] Gould, Transactions of the Institute of British Geographer 42 pp 53– (1967)
[14] Grimes, SIAM Journal on Analysis and Applications 11 pp 323– (1990)
[15] Paulino, International Journal for Numerical Methods in Engineering 37 pp 1511– (1994)
[16] Sabidussi, Mathematische Zeitschrift 72 pp 446– (1960)
[17] Weichsel, Proceedings of the American Mathematical Society 13 pp 47– (1962)
[18] Harary, Mathematica Scandinavica 20 pp 41– (1967)
[19] Pothen, SIAM Journal on Algebraic Matrix Analysis and Applications 11 pp 430– (1990)
[20] Kaveh, International Journal of Numerical Methods for Heat and Fluids 11 pp 358– (2001)
[21] Kaveh, Asian Journal of Civil Engineering 7 pp 147– (2006)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.