The Laplacian Matrix

The Laplacian matrix, denoted by L, is a real symmetric VxV matrix that may also be considered a kind of augmented vertex-adjacency matrix. It is defined as the following difference matrix (Mohar, 1989)  

It should be noted that the smallest eigenvalue of L is always equal to zero, as a consequence of the special structure of the Laplacian matrix. 

The Laplacian matrix is used to enumerate the number of spanning trees (e.g., Trinajstid et al., 1994 Nikolic et al., 1996). Let ns ranind the reader that a spanning tree of a graph G is a connected acyclic snbgraph containing all the vertices of G (Harary, 1971). 

When a polycyclic graph G is considered, obtaining the number of spanning trees is rather involved. One needs first to compute the Laplacian spectrum, and then to use it in the following counting formula, based on the matrix-tree theorem, in order to get the number of spanning trees of G (Mohar, 1989)  

Several topological indices based on the Laplacian matrix have been proposed, besides the number of spanning trees (Mohar, 1989 Kirby et al., 2004), the Mohar indices (Mohar, 1989 Trinajstic et al., 1994), the Wiener index of trees (Mohar, 1989, 1991 Mohar et al, 1993 Trinajstic et al, 1994), the quasi-Wiener index (Markovic et al., 1995), and spanning tree density and reciprocal spanning tree density (Mallion and Trinajstid, 2003). 

Before we start to calculate the Laplacian matrix we define the diagonal matrix DEG of a graph G. The non-diagonal elements are equal to zero. The matrix element in row i and column i is equal to the degree of vertex v/. 

Then the Lapladan matrix I of a simple graph G can be calculated from the diagonal matrix DEG and the adjacency matrix A following Eq. (11). 

---

The diagonalization of the Laplacian matrix gives A real eigenvalues "ki which constitute the Laplacian spectrum [Mohar, 1991b Trinajstic et al, 1994] and are conventionally labelled so that... 

The product of the positive A-l eigenvalues of the Laplacian matrix gives the spanning tree number T of the molecular graph Q as ... 

Also derived from the Laplacian matrix are the Mohar indices (TI)j and (TI)2, defined as ... 

The resistance distance between any pair of vertices can also be calculated by the Laplacian matrix as the following ... 

The Kirchhoff number can also be directly calculated from the Laplacian matrix by the following ... 

Klein et al.216 have also shown that the combinatorial Laplacian matrix L (often called just the Laplacian matrix ) is related to matrix // ... 

The difference matrix I-H is called the normalized Laplacian matrix Lnorm (also sometimes called just the Laplacian matrix) of G and there is much theory about it.230 The matrix Lnorm is clearly also related to the connectivity index ... 

An interesting relationship between the vertex-edge incidence matrix, the edge-vertex incidence matrix and the Laplacian matrix L was found as... 

The Laplacian matrix is also related to the vertex-edge and edge-vertex incidence matrices. 

With some analogy to the Laplacian matrix is the second path matrix, denoted by S and defined as [John and Diudea, 2004]... 

Unlike matrix MM, which usually is unsymmetrical, the matrix H is symmetric and related to MM by a similarity transformation, so that H and MM have the same eigenvalues and interrelated eigenvectors. The matrix H is also related to the Laplacian matrix moreover, the half sum of the elements of H coincides with the Randic connectivity index ... 

Ivanciuc, O. (2001g) Design of topological indices. Part 26. Structural descriptors computed from the Laplacian matrix of weighted molecular graphs modeling the aqueous solubility of aliphatic alcohols. Rev. Roum. Chim., 46, 1331-1347. 

The corresponding matrix L is symmetric and is referred to as the Laplacian matrix of the graph G- Note that some authors define the Laplacian to be the negative of our definition. The degree, or number of neighbors, of node i is fe,- = —L,-,-. 

Scriven [334] showed that the stability of spatially discrete homogeneous reaction-diffusion systems can be analyzed in terms of the structural modes of the network, i.e., the eigenvectors of the Laplacian matrix L. We have extended that approach [305], and the eigenvalues and eigenvectors of the matrix... 

Remark 13.1 The Laplacian matrix L is symmetric and therefore has real eigenvalues. 

Theorem 13.4 For a network ofn reactors represented by a graph Q the Laplacian matrix L is negative semideflnite. Moreover, = 0, and... 

The following Theorem addresses the question of how the eigenvalues of the Laplacian matrix change, when connections between reactors are removed or added in the network. It turns out that the eigenvalues of the smaller and the bigger graph interlace in an orderly arrangement. 

The following theorem establishes that the number of reactors in the network provides a lower bound for the spectrum of the Laplacian matrix of the network. 

This result and Theorem 13.5 imply that the eigenvalues p of the Laplacian matrix L associated with the structural modes of the network Q lie between 0 and -n, 0 > P > -n. This narrows the search for eigenvalue leading to instabilities of the uniform steady state of the network to eigenvalues of J(r) with 0 [Pg.372]

For two coupled reactors, the Laplacian matrix of the graph Q reads... 

Two different network topologies are possible for three coupled reactors (i) a linear array and (ii) a circular array. For three reactors, the latter coincides with global or all-to-all coupling. A linear array corresponds to the Laplacian matrix... 

A strict upper bound for tci ax is given by i sup = 3. Since this structural mode corresponds to the eigenvalue P2 of the Laplacian matrix L3iin, no Turing instability can occur in a linear three-reactor array if the mass-transfer coefficient k exceeds the value 3 in accordance with (13.59). 

The six different network topologies that occur for arrays of four coupled reactors are shown in Fig. 13.2. The Laplacian matrix L of each network can be read off from Fig. 13.2 and is given below. We also list the structural modes of L and the corresponding eigenvalues. 

---