Sign up ×

Given a regular directed graph $G(n,d)$, where $d$ is the total of in-degree dan out-degree and $n$ is the number of vertices (so that $G(n,d)$ has $dn$ edges). Let $A \in M_n (\{0,1\})$ matrix which is the adjacent matrix of $G(n,d)$.

Bollobas in Modern Graph Theory, Bela Bollobas, Springer Press proved that the number of the spanning tree of $G$ oriented to any fixed vertex is equal to $$t=\text{det} (C_{ij}(L))$$ where $C_{ij}$ denotes the cofactor, and $L=A-dI$ is a Laplacian Matrix. (note that since $G$ is regular the above quantity are equal and independent with respect to the choice of $i$ and $j$)

my question is: Given a number $t$ and $d$, how many graph $G(n,d)$ such that $t=\text{det} (C_{ij}(L))$? is there an efficient way to list all of them?

I've tried to bound the value of $n$, that is to have a lower bound of $t$ in terms of $n$ and $d$. One such way to do it, maybe to bound the eigenvalues of $C_{ij}(L)$.

share|cite|improve this question

Your Answer



Browse other questions tagged or ask your own question.