Spectra of some interesting combinatorial matrices related to oriented spanning trees on a directed graph

Athanasiadis, Christos A.

Journal of Algebraic Combinatorics, Tome 5 (1996) no. 1, pp. 5-11.

Résumé

Summary: 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.

Détail

Keywords: oriented spanning tree, $l$-walk, eigenvalue