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?

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ What is the difference between "no edge-cycle" and "no cycle"? $\endgroup$
    – darij grinberg
    Commented Sep 3, 2010 at 13:55
  • $\begingroup$ Or does "adjacent" mean "adjacent in the ambient graph"? $\endgroup$
    – darij grinberg
    Commented 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
    Commented Sep 3, 2010 at 14:51
  • 1
    $\begingroup$ So an edge-tree is what is more commonly called an induced tree, right? $\endgroup$
    – David Eppstein
    Commented 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$
    – David E Speyer
    Commented Sep 3, 2010 at 16:36

2 Answers 2

Reset to default
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$.

Improve this answer
$\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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I don't think the edge trees are required to be spanning trees. $\endgroup$
    – Gjergji Zaimi
    Commented 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$
    – Douglas S. Stones
    Commented 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
    Commented Sep 3, 2010 at 15:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .