Let $G$ be a finite connected graph on a $2m$-element vertex set $V$. For any graph with vertices $u,v$, let $\mu(u,v)$ denote the number of edges between $u$ and $v$. Suppose that $G$ has an automorphism $f$ that is a fixed-point free involution on the vertices. We can define a quotient graph $G/f$ by letting the vertices of $G/f$ be the orbits $[u]=\left\lbrace u,f(u)\right\rbrace$ of $f$, and setting $$ \mu([u],[v]) = \mu(u,v) + \mu(f(u),v). $$ Let $\kappa(H)$ denote the number of spanning trees of a graph $H$. By the Matrix-Tree Theorem and some simple linear algebra, one can show that $2\kappa(G)$ is divisible by $\kappa(G/f)$. My question is whether the factor of 2 is necessary, i.e., is it always true that $\kappa(G)$ is divisible by $\kappa(G/f)$? Similar questions can be asked for more complicated automorphism groups of $G$.

  • $\begingroup$ I think this works in the general case too if we define a quotient according to $\mu([u],[v])=\mu(u,v)+\mu(u,f(v))+\cdots+\mu(u,f^{n-1}(v))$, where $f$ is an automorphism of degree $n$, but I havent checked the details. I wonder if there are any other graph related quantities that behave this way under taking quotients. $\endgroup$ – Gjergji Zaimi Jun 4 '10 at 14:40

Let us group the vertices as $U=\{u_1,u_2,\dots,u_n\}$ and $V=\{v_1,v_2,\dots, v_n\}$ where $f(u_i)=v_i$. Let $L_0$ be the laplacian of the graph with vertex set $U$ and edges as restricted from $G$, let $L _1 = \operatorname{diag}\left( \sum _{j=1}^n \mu(u _i, v _j)\right)$ and $L=L _0+L _1$, also let $A$ be the symmetric matrix whose $a _{ij}$ entry is $-\mu(u _i,v _j)$. Clearly the Laplacian of $G$ is $M=\left( \begin {array} {cc} L & A \\\ A & L \end {array} \right)$. Let $M^*$ stand for the matrix $M$ with deleted first row and column. We have $$\kappa(G)=\det \left( \begin {array} {cc} L & A \\\ A & L \end {array} \right) ^ *=\det \left( \begin {array} {cc} B & C \\\ D & (L+A)^ * \end {array} \right)$$ for some block matrices $B,C,D$ of size $n\times n,n\times (n-1),$ and $(n-1)\times n$ where this second matrix was obtained by adding the $i$th row of $M^{*}$ to it's $n+i$th row for $1\le i\le n-1$ and then adding the first (or last) $n-1$ columns to the $n$th column. So $D$ is the matrix $(L+A)^*$ together with a last column of zeros, making $\left((L+A)^*\right)^{-1}D$ with integer entries. Next we factor it using one of these identities $$\kappa(G)=\det(L+A)^ * \det(B-C\left((L+A)^*\right)^{-1}D)$$ and observe that $L+A$ is the Laplacian of $G/f$ so $\det(L+A)^ *=\kappa(G/f)$, and since the second factor is an integer we get the desired divisibility.

| cite | improve this answer | |
  • $\begingroup$ The proof looks o.k. now. Getting the last column of zeros was a key step. Thanks for your answer! $\endgroup$ – Richard Stanley Jun 21 '10 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.