5
$\begingroup$

Are there any results on the number of subgraphs in a labeled tree (or a general labeled graph)? I would also be happy to know any results on the number of subgraphs in an unlabeled tree. Cayley's formula says how many different trees I can form given n vertices, but it doesn't seem to relate to the problem of counting subgraphs in a given tree. Any help is appreciated.

$\endgroup$
11
  • 2
    $\begingroup$ Do you mean connected subgraphs? Otherwise it seems trivial. $\endgroup$ Jan 27, 2012 at 12:32
  • $\begingroup$ @Brendan, how does allowing the subgraphs to be disconnected make things trivial? When I count the number of subgraphs of trees consisting of n-point paths, for example, I get the every-other-Fibonacci sequence 2,5,13,34,89,.... That doesn't seem deep, but it doesn't feel trivial. Or am I not understanding the problem? $\endgroup$ Jan 27, 2012 at 18:59
  • $\begingroup$ My take is (since the vertices are labeled) the number of subgaphs is about 2^E, where E is the number of edges in the original graph. Brendan may have something deeper in mind than this though. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 $\endgroup$ Jan 27, 2012 at 19:21
  • $\begingroup$ @Gerhard, if you retain all the vertices, then the number of subgraphs is clearly 2^E. But as you erase edges, you're also allowed to erase certain vertices, which is why my n-point path example produces something asymptotically proportional to phi^2n. $\endgroup$ Jan 27, 2012 at 19:32
  • $\begingroup$ Yes. Do you retain the labels? If you do, the answer is still 2^E. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 $\endgroup$ Jan 27, 2012 at 19:52

2 Answers 2

3
$\begingroup$

The following algorithm should efficiently calculate the answer for the number of subtrees of a labeled graph.

Let $(T, r)$ be a labeled, rooted tree with root $r$. We first calculate the number of subtrees containing $r$. Call this value $N_1(T, r)$. If $r_1, \dots, r_k$ are the neighbors of $r$ and $T_1,\dots, T_k$ are the trees of $T-r$ such that $r_i \in V(T_i)$ for $1 \le i \le k$, then

$N_1(T, r) = \prod_1^k \left( N_1(T_i, r_i) + 1 \right).$

This follows because for each neighbor $r_i$ of $r$, we have a choice of $N_1(T_i, r_i)$ possible trees or alternatively, the empty tree.

This formula gives a recursive algorithm to calculate $N_t(T, r)$. Since the total number of vertices in the trees decreases in each iteration of the algorithm, we get an easy $O(n^2)$ bound on the run-time.

For a labeled tree $T$, let $N(T)$ be the number of distinct subtrees. Fix a leaf $v$ of $T$. Then $N(T) = N(T-v) + N_1(T, v)$. Thus, again we get a recursive algorithm with a bound of $O(n^3)$ on the run-time. It might be possible to get better bounds on the run-time of the algorithms.

The specific value of $N(T)$ will depend a lot on the tree $T$. For example, if $T$ is the path on $n$ vertices, then $N(T) = O(n^2)$. Alternatively, if $T$ is the star on $n$ vertices, then $N(T) = O(2^n)$.

$\endgroup$
1
  • $\begingroup$ This is also what I came up when putting some time towards the problem. Basically, star is the worst case with O(2^n) different subgraphs, and I was mainly interested in the worst case behavior. I think it's also possible to show an O(2^n) bound for a complete binary tree. $\endgroup$
    – filox
    Jan 27, 2012 at 23:15
5
$\begingroup$

Paul's idea can be improved into a linear algorithm to count the subtrees of a tree. Arbitrarily root the tree at some vertex $r$ and let $T_x$ denote the subtree rooted at vertex $x$. Define $A(x)$ to be the number of subtrees of $T_x$ that include $x$, and define $B(x)$ to be the number of subtrees of $T_x$ that don't include $x$. Do not include the null subtree in $B(x)$ (add 1 to the final answer if you want).

If $x$ is a leaf then $A(x)=1$ and $B(x)=0$.

If $y_1,\ldots,y_k$ are the children of a non-leaf $x$, then \begin{align*} A(x) &= \prod_{i=1}^k (1+A(y_i)) \\\\ B(x) &= \sum_{i=1}^k (A(y_i) + B(y_i)), \end{align*} and the answer is $A(r)+B(r)$.

The two recurrences need to be applied once for each vertex. The time required for vertex $x$ is $O(1+\text{degree of }x)$, which adds up to $O(n)$ when summed over all $x$. So the total time is $O(n)$. Here we are cheating slightly by counting arithmetic operations as $O(1)$ even though numbers with a linear number of bits might be involved.

This is most unlikely to be original.

$\endgroup$
1

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.