Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE NINTH INTERNATIONAL CONFERENCE ON CIVIL AND STRUCTURAL ENGINEERING COMPUTING
Edited by: B.H.V. Topping
An Efficient Method for Decomposition of Regular Structures using Algebraic Graph Theory
A. Kaveh and H. Rahami
Department of Civil Engineering, Iran University of Science and Technology, Narmak, Tehran, Iran
A. Kaveh, H. Rahami, "An Efficient Method for Decomposition of Regular Structures using Algebraic Graph Theory", in B.H.V. Topping, (Editor), "Proceedings of the Ninth International Conference on Civil and Structural Engineering Computing", Civil-Comp Press, Stirlingshire, UK, Paper 11, 2003. doi:10.4203/ccp.77.11
Keywords: graphs, regular structures, strong Cartesian product, direct product,.
Algebraic graph theory can 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 our fundamental understanding of graphs.
One of the major contributions in algebraic graph theory is due to Fiedler , where the properties of the second eigenvalue and eigenvector of the Laplacian of a graph have been introduced. This eigenvector, known as the Fiedler vector is used in graph nodal ordering and bipartition.
General methods are available in literature for calculating the eigenvalues of matrices, however, for matrices corresponding to special models, it is beneficial to make use of their extra properties.
In this paper an efficient method is presented for calculating the eigenvalues of regular structural models. A structure and correspondingly its graph model are called regular if they can be viewed as the direct or strong Cartesian product of some simple graphs known as their generators. The eigenvalues of the adjacency and Laplacian matrices for a regular graph model are easily obtained by the evaluation of eigenvalues of its generators. The second eigenvalue of the Laplacian of a graph is also obtained using a much faster and much simple approach than the existing methods
Many structures have regular patterns and can be viewed as the strong Cartesian product or direct product of a number of simple graphs. These subgraphs used in the formation of a model are called the generators of that model. The Cartesian product of two graphs is used for nodal ordering and domain decomposition by Kaveh and Rahami [1,2]. In the following two other products are employed for graph partitioning and domain decomposition.
The strong Cartesian product of the graphs and , denoted by has its node set as the Cartesian and nodes and of being adjacent with respect to the strong product if
For direct product the node set is . Two nodes and are adjacent when and .
The following two theorems are used for calculating the eigenvalues for the Laplacian matrix of the products of two graphs:
Theorem 1: Let and be the eigenvalues of the adjacency matrices of and , respectively. Then eigenvalues of are for and .
Theorem 2: Let and be the eigenvalues of the adjacency matrices of and , respectively. Then eigenvalues of are for and .
Formulae are derived for calculating the second eigenvalues of the Laplacian matrices. The second eigenvectors are then obtained, and the bisection of the models are performed. This can be achieved by arranging the entries of in an ascending order and partitioning the nodes into two subsets according to their occurrence in .
purchase the full-text of this paper (price £20)