Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a cubic graph $G$ with $\tau(G)$ spanning trees. Now I replace each vertex in $G$ by a triangle giving me a new graph $G'$ - this operation is sometimes referred to as blowing up the vertex to a triangle or truncating the vertex. I want to find a formula for the number of spanning trees in $G'$.

For example, the complete graph on 4 vertices $K_4$ has 16 vertices, and blowing up each vertex in $K_4$ gives a graph on 12 vertices with 6000 spanning trees. If it is not possible to give a formula for blowing up the vertices in a general cubic graph, a formula for the specific case where the starting graph is $K_4$ is much appreciated.

As an example of how the operation works, I have provided a drawing of the graph obtained from performing the operation once on $K_4$.

alt text

share|improve this question
So what you really want is derive an identity for the spectrum of the truncated graph with relation to the spectrum of the original graph. By spectrum I mean the eigenvalues of the adjacency or Laplacian matrix. In this case it does not matter. –  Jernej Dec 15 '12 at 11:31
What exactly is the adjacency among the triangles? If $T_u,T_v$ are triangles that were obtained from two adjacent vertices $u,v$ then every vertex of $T_v$ is adjacent to every vertex of $T_u$? –  Jernej Dec 15 '12 at 11:47
I have provided an image of $K_4$ after the operation has been applied. –  utdiscant Dec 15 '12 at 12:04
Here are the next few values of the number of spanning trees for blowup graphs obtained by taking $K_4$ as a start $$16, 6000, 113906250000, 280568536600470542907714843750000$$ let me know if you want some other values relative to other starting graphs. As for the main question,try to express the adjacency matrix of the blowup graph and see if you can find its eigenvalues in terms of $K_3$ and the base graph. –  Jernej Dec 15 '12 at 12:23
one just need to worry about the product of nonzero eigenvalues, rather than individual eigenvalues. –  Dima Pasechnik Dec 15 '12 at 14:04
add comment

1 Answer

up vote 7 down vote accepted

The resulting graph is the linegraph of the subdivision graph of $G$. This survey paper of Bojan Mohar tells how to obtain the Laplacian spectrum of the linegraph of a semiregular graph and the subdivision graph of a regular graph.

Let's generalize. Let $G$ be a regular graph of $n$ vertices, degree $d$, and therefore $m=nd/2$ edges. Let $\mu(G,x)$ denote the characteristic polynomial of the Laplacian matrix, and let $\kappa(G)$ be the number of spanning trees.

The blowup $B(G)$ of $G$, formed by replacing each vertex by a $d$-clique, is the linegraph of the subdivision graph of $G$. Using Theorems 3.8 and 3.9 in the survey paper of Mohar, we find $$ \mu(B(G),x) = (-1)^n (x-d)^{m-n} (x-d-2)^{m-n} \mu(G,x(d+2-x)). $$

We know that $\kappa(G) = n^{-1} (-1)^{n-1} \mu'(G,0)$. Differentiating and using $\mu(G,0)=0$, we find $$ \kappa(B(G)) = d^{m-n-1} (d+2)^{m-n+1} \kappa(G). $$

For the $k$-fold blowup, we have $$ \kappa(B^k(G)) = d^{d_k(m-n)-k} (d+2)^{d_k(m-n)+k} \kappa(G), $$ where $d_k=1+d+\cdots+d^{k-1}$.

For $d=3$, I believe this gives $$ \kappa(B^k(G)) = (5/3)^k 15^{(3^k-1)n/4} \kappa(G). $$

share|improve this answer
add comment

Your Answer


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

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