Keywords: algebraic graph theory, Laplacian, adjacency, symmetry, eigenvalue, Fiedler vector, factors, graph product, ordering, bisection.

The representation of a finite graph by a matrix, provides an immediate link between linear algebra and graph theory. In fact the algebraic graph theory, in a way, can be considered as an attempt to utilize linear algebra including the well-developed theory of matrices for the purpose of graph theory and its applications. Algebraic graph theory offers the pleasure of seeing many unexpected and useful connections between two beautiful parts of mathematics, namely algebra and graph theory.

Algebraic graph theory can also be considered as a branch of graph theory, where eigenvalues and eigenvectors of certain matrices are employed to deduce the principal properties of a graph. In fact, eigenvalues are closely related to most of the invariants of a graph, linking one extremal property to another. These eigenvalues play a central role in fundamental understanding of graphs.

The adjacency and Laplacian matrices of graphs and their eigenvalues and eigenvectors play the most important role in algebraic graph theory. These two matrices will collectively be called graph matrices. In the other hand the pattern equivalence of the graph matrices and structural matrices provide immediate connection between algebraic graph theory and structural mechanics [1,2].

One of the major contributions in algebraic graph theory is due to Fiedler [3], who introduced the properties of the second eigenvalue and eigenvector of the Laplacian of a graph.

This paper consists of seven sections. After an introductory section, basic concepts and definitions are presented from algebraic graph theory in Section 2. Subsequent sections contain various applications of this theory in structural mechanics. Nodal ordering for bandwidth, profile and wavefront optimisation is discussed in Section 3. Spectral bisection is presented in Section 4 using second eigenvalue of the Laplacian matrices of graph models. Graph factorisation based on matrix algebra for different symmetric forms is discussed in Section 5, Refs [4,5]. Such factorisations have applications in studying the dynamic behaviour of mass-spring systems, free vibration and stability analysis of frame structures. Section 6 contains extremely fast analytical methods for evaluating eigenvalues and eigenvetors of regular structures and finite element meshes, Ref. [6]. This is based on concepts from graph products, extensively studied in the last decade. A brief discussion is provided at the end of each section, and concluding remarks form the final section of this paper.

Algebra combined with the theory of graphs results in a powerful means for the solution of many problems in structural mechanics. The eigenvalues and eigenvectors of graph matrices provide a wealth of information about the topological properties of structures and finite element models. Factorisation of graph models of structures results in a considerable simplification in studying the large-scale problems. The basic components of models, when identified, lead to extremely powerful tools for exploring the properties of the constituting model.

1

Kaveh, A., "Structural Mechanics: Graph and Matrix Methods", Research Studies Press, 3rd edition, UK, 2004.

2

Kaveh, A. "Optimal Structural Analysis", Research Studies Press, 2nd edition, UK, 2004.

3

Fiedler, M., "Algebraic connectivity of graphs", Czechoslovak Mathematical Journal, 23,(1973)298-305.

4

Kaveh, A. and Sayarinejad, M.A., "Eigensolutions for matrices of special patterns", Communications in Numerical Methods in Engineering, 19,(2003)125-136. doi:10.1002/cnm.576

5

Kaveh, A. and Sayarinejad, M.A., "Eigensolutions for factorable matrices of special patterns", Communications in Numerical Methods in Engineering, No. 2, 20 (2004)133-146. doi:10.1002/cnm.656

6

Kaveh, A. and Rahami, H., "An efficient method for decomposition of regular structures using graph products", International Journal of Numerical Methods in Engineering, to appear, 2004. doi:10.1002/nme.1126

purchase the full-text of this chapter (price £20)

go to the previous chapter
go to the next chapter
return to the table of contents
return to the book description
purchase this book (price £90 +P&P)