When I was an undergraduate graph theory was a subject which seemed to me completely uninteresting and I very consciously chose not to attend a lecture course on the subject. In the meantime I have realized that having become interested in reaction networks I could profit from knowing more about graph theory. One result which plays a significant role is the matrix-tree theorem. It asserts the equality of the number of subgraphs of a certain type of a given graph and a certain determinant. This could be used to calculate numbers of subgraphs. On the other hand, it could be used in the other direction calculate determinants and it is the second point of view which is relevant for reaction networks.

For the first part of the discussion here I follow these notes. If is an (unoriented) graph then a spanning tree is a connected subgraph which includes all vertices of and contains no cycles. The graph Laplacian of is the matrix for which is equal to the number of edges containing the vertex , if and there is an edge joining vertex to vertex and otherwise. The first version of the matrix tree theorem, due to Kirchhoff, says that the number of spanning trees of can be calculated in the following way. Choose any vertex of and remove the th row and th column from to get a matrix . Then compute the determinant of . Surprisingly the value of the determinant is independent of . The first version of the theorem can be obtained as a consequence of a second more sophisticated version proved a hundred years later by Tutte. This concerns directed graphs. A vertex is said to be accessible from if there is a directed path from to . A vertex in a directed graph is called a root if every other vertex is accessible from it. A directed tree is a directed subgraph which contains a root and which, when the orientation is forgotten, is a tree (i.e. it is connected and contains no unoriented cycles). There is then an obvious way to define a spanning rooted tree. To formulate the second version of the theorem we introduce the matrix Laplacian of the directed graph. If the entry is the number of edges with final vertex . if and there is a directed edge from to . if and there is no edge connecting and . The statement of the theorem is that the number of rooted trees with root is equal to the determinant of , a matrix derived from as before. To see that the first version of the theorem follows the second first associate an oriented graph to an unoriented one by putting in oriented edges joining a pair of vertices in both directions whenever they are joined by an edge in the original graph. Then there is a bijection between trees rooted at in the unoriented graph and oriented trees rootes at in the oriented graph. On the other hand the two graphs have the same Laplacian since the number of edges ending at a vertex in the oriented graph is the same as the number of edges having that endpoint in the unoriented graph.

What is the connection of all this with reaction networks? Consider a chemical reaction network with only monomolecular reactions and reaction coefficients all equal to one. Then under mass action kinetics the evolution equations for the concentrations are , where is the Laplacian matrix of the network. There is a conserved quantity, which is the sum of the concentrations of all species. A steady state is an element of the kernel of . The next part of the discussion follows a paper of Gunawardena (PLoS ONE, 7(5), e36321). He allows general reaction constants. The notion of the Laplacian is extended correspondingly. If the network is strongly connected (in the terminology of graph theory) or weakly reversible (in the terminology of chemical reaction network theory) the kernel of the Laplacian matrix is one-dimensional. Thus there is precisely one steady state in each stoichiometric compatibility class. It is moreover possible to compute a vector spanning the kernel of by graph theoretical methods. This also goes back to Tutte. To get the th component first take the product of the reaction constants over a rooted tree and then sum these quantities over the rooted trees with root . More generally the dimension of the kernel of is equal to the number of terminal strong linkage classes. It is also revealed there that the Laplacian corresponds to the matrix considered by Horn and Jackson. These ideas are also related to the King-Altman theorem of enzyme kinetics. I have the impression that I have as yet only scratched the surface of this subject. I hope I will be able to come back and understand more about it at a later date.

## Leave a Reply