Computational Technology Resources - CCP

Keywords: graphs, regular structures, strong Cartesian product, direct product,.

Summary

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 [1], 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 $G = K\otimes H$ has its node set as the Cartesian $V(K\otimes H)=V(K)\times V(H)$ and nodes and of $K\otimes H$ being adjacent with respect to the strong product if

and $vy\in E(H)$ , or
$ux\in E(K)$ and , or
$ux\in E(K)$ and $vy\in E(H)$ .

For direct product $K\ast H$ the node set is $V(K) \times V(H)$ . Two nodes and are adjacent when $u_1v_1\in E(K)$ and $u_2v_2 \in E(H)$ .

The following two theorems are used for calculating the eigenvalues for the Laplacian matrix of the products of two graphs:

Theorem 1: Let $\lambda_1,\lambda_1,\ldots,\lambda_m$ and $\mu_1,\mu_2,\ldots,\mu_n$ be the eigenvalues of the adjacency matrices of and , respectively. Then $m\times n$ eigenvalues of $G = K\otimes H$ are $\left\{ \lambda_i+\mu_j+\lambda_i\mu_j \right\}$ for $i=1,\ldots,m$ and $j=1,\ldots,n$ .

Theorem 2: Let $\lambda_1,\lambda_1,\ldots,\lambda_m$ and $\mu_1,\mu_2,\ldots,\mu_n$ be the eigenvalues of the adjacency matrices of and , respectively. Then $m\times n$ eigenvalues of $G=K\ast H$ are $\left\{\lambda_i\mu_j\right\}$ for $i=1,\ldots,m$ and $j=1,\ldots,n$ .

Formulae are derived for calculating the second eigenvalues of the Laplacian matrices. The second eigenvectors $\mathbf{v}_2$ are then obtained, and the bisection of the models are performed. This can be achieved by arranging the entries of $\mathbf{v}_2$ in an ascending order and partitioning the nodes into two subsets according to their occurrence in $\mathbf{v}_2$ .

References

1: M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 23(1973)298-305.
2: A. Kaveh and H. Rahami, A New Spectral Method for Nodal Ordering of Regular Space Structures, 2003, submitted for publication. doi:10.1016/j.finel.2003.11.007
3: A. Kaveh and H. Rahami, An efficient spectral method for bisection of regular finite element meshes, 2003, submitted for publication.

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

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

	Computational & Technology Resources an online resource for computational, engineering & technology publications
	not logged in - login
Front Page Browse CCP CSETS CTR IJRT Other Authors Search Purchase Guide FAQ Contact us	Civil-Comp Proceedings ISSN 1759-3433 CCP: 77 PROCEEDINGS OF THE NINTH INTERNATIONAL CONFERENCE ON CIVIL AND STRUCTURAL ENGINEERING COMPUTING Edited by: B.H.V. Topping Paper 11 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 doi:10.4203/ccp.77.11 purchase the full-text of this paper Full Bibliographic Reference for this paper 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,. Summary 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 [1], 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 $G = K\otimes H$ has its node set as the Cartesian $V(K\otimes H)=V(K)\times V(H)$ and nodes and of $K\otimes H$ being adjacent with respect to the strong product if and $vy\in E(H)$ , or $ux\in E(K)$ and , or $ux\in E(K)$ and $vy\in E(H)$ . For direct product $K\ast H$ the node set is $V(K) \times V(H)$ . Two nodes and are adjacent when $u_1v_1\in E(K)$ and $u_2v_2 \in E(H)$ . The following two theorems are used for calculating the eigenvalues for the Laplacian matrix of the products of two graphs: Theorem 1: Let $\lambda_1,\lambda_1,\ldots,\lambda_m$ and $\mu_1,\mu_2,\ldots,\mu_n$ be the eigenvalues of the adjacency matrices of and , respectively. Then $m\times n$ eigenvalues of $G = K\otimes H$ are $\left\{ \lambda_i+\mu_j+\lambda_i\mu_j \right\}$ for $i=1,\ldots,m$ and $j=1,\ldots,n$ . Theorem 2: Let $\lambda_1,\lambda_1,\ldots,\lambda_m$ and $\mu_1,\mu_2,\ldots,\mu_n$ be the eigenvalues of the adjacency matrices of and , respectively. Then $m\times n$ eigenvalues of $G=K\ast H$ are $\left\{\lambda_i\mu_j\right\}$ for $i=1,\ldots,m$ and $j=1,\ldots,n$ . Formulae are derived for calculating the second eigenvalues of the Laplacian matrices. The second eigenvectors $\mathbf{v}_2$ are then obtained, and the bisection of the models are performed. This can be achieved by arranging the entries of $\mathbf{v}_2$ in an ascending order and partitioning the nodes into two subsets according to their occurrence in $\mathbf{v}_2$ . References 1 M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 23(1973)298-305. 2 A. Kaveh and H. Rahami, A New Spectral Method for Nodal Ordering of Regular Space Structures, 2003, submitted for publication. doi:10.1016/j.finel.2003.11.007 3 A. Kaveh and H. Rahami, An efficient spectral method for bisection of regular finite element meshes, 2003, submitted for publication. purchase the full-text of this paper (price £20) go to the previous paper go to the next paper return to the table of contents return to the book description purchase this book (price £123 +P&P)
Back to top	©Civil-Comp Limited 2023 - terms & conditions