9
$\begingroup$

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 spanning trees, 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(source)

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Jernej
    Dec 15, 2012 at 11:31
  • $\begingroup$ 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$? $\endgroup$
    – Jernej
    Dec 15, 2012 at 11:47
  • $\begingroup$ I have provided an image of $K_4$ after the operation has been applied. $\endgroup$
    – utdiscant
    Dec 15, 2012 at 12:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jernej
    Dec 15, 2012 at 12:23
  • $\begingroup$ one just need to worry about the product of nonzero eigenvalues, rather than individual eigenvalues. $\endgroup$
    – Dima Pasechnik
    Dec 15, 2012 at 14:04

1 Answer 1

Reset to default
11
$\begingroup$

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). $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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