ISSN:
1572-9192
Keywords:
oriented spanning tree
;
l-walk, eigenvalue
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract The Laplacian of a directed graph G is the matrix L(G) = O(G) −, A(G) where A(G) is the adjaceney 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00186525
Permalink
