Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.