on counting of special case of trees on a graph - MathOverflow

on counting of special case of trees on a graph

2010-09-03T13:38:20Z

Lets define edge-cycle in a graph $G$ as a path where the first and the last node are adjacent. (in contrast with the definition of cycle where first and last node are the same).

An edge-tree $T$ is a tree with the additional property that doesn't have an edge-cycle.

In a graph we can compute the number of spanning trees by using the Matrix-Tree theorem.

Is there any similar theorem for the computation of the number of edge-trees of a graph?

Answer by Nekura for on counting of special case of trees on a graph

2010-09-03T14:47:41Z

If I'm reading your definitions right, I believe the answer is that there are zero edge-trees of G if G has any cycle. And one if G is a tree itself (T=G)

Proof: If G has a cycle C, then for any spanning tree T of G there exist an edge E(u,v) of C that is not in T. Since T is a spanning tree, there is a path from u to v in T, and u and v are adjacent in G, thus the path from u to v is an edge-cycle, therefore there is always an edge-cycle in T. Therefore there are zero edge-trees of G.

Answer by Tony Huynh for on counting of special case of trees on a graph

2010-09-03T16:27:03Z

I'll answer a question raised in the comments:

Problem: Count the number of induced trees of size $k$.

According to this paper by Erdös, Saks and Sos, it is NP-complete to decide given a graph $G$ and an integer $k$, if $G$ contains an induced tree of size $k$. So, it's probably pretty damn hard to count them. Apparently, it remains NP-complete even for bipartite graphs.

Actually, the argument is pretty simple so I'll include it here. Given a graph $H$ and an integer $k$, it is well-known that the problem of deciding if $H$ has an independent set of size $k$ is NP-complete. Suppose that $H$ has $n$ vertices. Let $G$ be the graph obtained from $H$ by first adding a disjoint copy of $P_n$ (a path on $n$ vertices), and then connecting one end of $P_n$ to all the vertices in $H$. Clearly, $H$ has an independent set of size $k$ if and only if $G$ contains an induced tree of size $n+k$.