2.16 The Generalized Laplacian Matrix

Gutman et al. [173] proposed a simple method for computing the number of spanning trees of planar polycyclic graphs. It is based on the vertex-weighted inner dual of polycyclic graphs. An inner dual G' of a planar polycyclic graph G is obtained by placing a vertex in each cycle of G and a pair of vertices in G' is connected if the corresponding cycles in G have an edge in common. In a vertex-weighted inner dual, vertices are weighted by the numbers representing the sizes of the corresponding cycles. In Figure 22, we give the anthracene graph G10 and its weighted inner dual G11 with weights denoted by x:

G10                                                       G11

Figure 22. Anthracene graph and its vertex-weighted inner dual.

The Generalized Laplacian matrix, that is, the Lapalacian matrix of the weighted inner dual is given by:

L = [wΔ - vA]                                                  (31)

where wΔ is the weighted diagonal matrix and vA is the vertex-adjacency matrix of the vertex-weighted inner dual. The determinant of the generalized Laplacian matrix gives the polynomial of the weighted inner dual. Substituting the values of vertex-weights by the cycle sizes, one obtains the number of spanning trees.

The application of this procedure is demonstrated below for the anthracene graph and its weighted inner dual. The wΔ and vA matrices of the weighted inner dual G11 are as follows:

wΔ(G11)=
x
0
0
0
x
0
0
0
x

vA(G11)=
0
1
0
1
0
1
0
1
0

and the corresponding generalized Laplacian polynomial of G11 is:

det|L(G11)|=det
x
-1
0
 
-1
x
-1
= x3 -2x
0
-1
x
                               (32) 

Substituting 6 for x in (32), the number of spanning trees obtained for anthracene graph is 204.

To demonstrate how the cycle sizes influence the number of spanning trees of a polycyclic graphs, we compute this number for a tricyclic graph corresponding to benzo[f]azulene. This graph and its vertex-weighted inner dual are shown in Figure 23.

Figure 23. Benzo[f]azulene graph and its vertex-weighted inner dual.

The generalized Laplacian polynomial of the inner dual of the benzo[f]azulene graph is given by:

det|L(G13)|=det
x
-1
0
 
-1
y
-1
= xyz -x - z
0
-1
z
                               (33) 

The sizes of cycles in the benzo[f]azulene graph are x=6, y=7 and z=5. Substitution of these numbers in above polynomial (33) gives the number of spanning trees of G12 as 199.

This approach by Gutman et al. [173] for counting spanning trees applies only to planar polycyclic graphs. Later Kirby et al. [167] put forward a theorem for counting spanning trees in general molecular graphs, that is, non-planar graphs with loops and multiple edges, with particular application to toroidal fullerenes.The approach by Kirby et al. [167] is based on the following counting formula:

t(G) = det V/(det U)2                 (34)

where the V-matrix is defined as:

V = (CE)(CE)T                 (35)

and the U-matrix is a non-singular matrix chosen in such a way that its determinant is 1 or some small integer. The CE-matrix is a cycle-edge incidence matrix, the inverse of the edge-cycle incidence matrix (see section 3.4).

Kirby et al. [167] considered three kinds of cycles: independent cycles, fundamental cycles and patch cycles and showed that they all produce the same number of spanning trees. However, det U is equal to 1 only for fundamental cycles of any graph and for patch cycles of any planar graph. It should be noted that the procedure set up by Kirby et al. [167] reduces for planar graphs to that introduced by Gutman et al. [173].

<< . . . >>