Return to Question

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

(source)

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

(source)

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 http://s18.postimage.org/cgnyvoi89/image.png

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

(source)

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.

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 http://s18.postimage.org/cgnyvoi89/image.png