Keywords: graph product, Cartesian product, strong Cartesian product, direct product, eigenproblem, regular graph.

In this paper, a topological method is presented to obtain the eigensolution of a cylindrical-shaped grid from those of a plane grid. Similarly, the properties of a torus-shaphed grid is calculated from those of a cylindrical-shaped grid. This method simplifies the evaluation of the Fiedler vectors to be employed in the ordering and graph partitioning of regular structural models, for optimal structural analysis.

Consider a planar grid produced as the Cartesian product of two paths , with . The grid is bent and the two edges along are connected to each other by disjoint members, producing a cylindrical-shaped grid . Naturally, the number of nodes of and are identical, and has members more than . Similarly, a torus-shaped grid is formed from by the addition of members to its free edges, as shownm in Figure 95.1

In this paper it is proved that . Thus, without considering specific values for and , and only by assuming , it is concluded that the second eigenvalue of is the same as the third eignvalue of .

As an example, for and , we have

Similarly, it can be proved that the third eigenvalue and the second eigenvalue are identical; i.e. .

For direct and strong Cartesian products the same results are applicable, and and .

As an example, for and , the following results can be observed:

The eigenvalues of the adjacency and Laplacian matrices of three different graph products, provide an efficient approach for calculating the eigenvalues of adjacency and Laplacian matrices of weighted and non-weighted graphs. The eigensolution of graphs has many applications in computational mechanics. Examples of such applications are nodal and element ordering for bandwidth, profile and frontwidth optimization, graph partitioning, and subdomaining of finite element models [1,2]. The present forms are also effective tools for calculating eigenvalues and eigenvectors of matrices arising form numerical methods for differential equations applied to structural mechanics problems.

1

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

2

Kaveh A. "Optimal Structural Analysis", Research Studies Press, Somerset, U.K., 1997.

3

Kaveh, A. and Rahami, H., "A unified method for eigendecomposition of graph products", Communications in Numerical Methods in Engineering, 2005, in press. doi:10.1002/cnm.753

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 £135 +P&P)