JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 5, No 1 (1996)

Christos A. Athanasiadis

The Laplacian of a directed graph G is the matrix L( G) = O( G) - A( G), where A( G) is the adjacency matrix of G and O( G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A( G). Given a directed graph G we construct a derived directed graph D( G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D( G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D( G) for some specific directed graphs G. A recent conjecture of Propp for D( H _n) follows, where H _n stands for the complete directed graph on n vertices without loops.

1. V. Anantharam and P. Tsoucas, "A proof of the Markov chain tree theorem," Stat. Probab. Letters 8 (1989), 189-192.
2. S. Chaiken and D.J. Kleitman, "Matrix tree theorems," J. Combin. Theory Ser. A 24 (1978), 377-381.
3. A. Edelman, private communication.
4. N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, "Alternating sign matrices and domino tilings," J. Alg. Combin. 1 (1992), 111-132.
5. R. Merris, "Laplacian matrices of graphs: A survey," Linear Algebra Appl. 197, 198 (1994), 143-176.
6. J. Propp, private communication.
7. J. Propp, "Lattice structure for orientations of graphs," unpublished manuscript dated October 1, 1993.