1
$\begingroup$

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?

$\endgroup$
13
  • 2
    $\begingroup$ What is the difference between "no edge-cycle" and "no cycle"? $\endgroup$ Sep 3, 2010 at 13:55
  • $\begingroup$ Or does "adjacent" mean "adjacent in the ambient graph"? $\endgroup$ Sep 3, 2010 at 13:55
  • 1
    $\begingroup$ Well, technically katsarola wanted to count edge-trees, not necessarily spanning edge trees, even though the Matrix-Tree theorem counts spanning trees. If spanning edge-trees are wanted, then there is 1 if the graph is a tree, and none otherwise. If it's edge-trees that are wanted, it looks like we just want to count induced subgraphs that are trees. $\endgroup$
    – Tony Huynh
    Sep 3, 2010 at 14:51
  • 1
    $\begingroup$ So an edge-tree is what is more commonly called an induced tree, right? $\endgroup$ Sep 3, 2010 at 15:57
  • 3
    $\begingroup$ The point of this comment is to explain why your definition is the same as "induced trees". Let S be a set of vertices of G. Let H by the subgraph induced by S en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs. I claim that there is an edge-tree with vertex set S if and only if H is a tree. Proof: Clearly, if H is a tree, it is an edge tree. Now, let T be a tree with vertex set S. Suppose that (u,v) is an edge of H not in T. Trees are connected, so there is a path through T from u to v. Adding the edge (u,v) to this path shows that T is not an edge-tree. $\endgroup$ Sep 3, 2010 at 16:36

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I don't think the edge trees are required to be spanning trees. $\endgroup$ Sep 3, 2010 at 14:56
  • $\begingroup$ I thought this too initially (but it's not right). Take the 3-cycle on vertices {a,b,c}, add a vertex e and an edge between a and e. Then eabc and eacb are both spanning trees whose endpoints are not adjacent. $\endgroup$ Sep 3, 2010 at 15:03
  • 2
    $\begingroup$ But eabc is not a spanning edge-tree, since it contains abc which is an edge cycle. $\endgroup$
    – Tony Huynh
    Sep 3, 2010 at 15:07

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.