1
$\begingroup$

Let G be a tree-structured graph. A connected induced subgraph is an induced subgraph from G that is connected. (Since the original graph is a tree, any connected induced subgraph is also a tree)

My question: Given a tree G of n vertices, how many connected induced subgraph can be obtained from G?

An example: n = 4, G looks like 1---2---3---4 (I name those four vertices by 1, 2, 3, 4). Then we have 10 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,2,3}, {2,3,4}, {1,2,3,4} where I represent a connected induced subgraph by a set of their vertices.

Another example: n = 4, G looks like 1---2---3, 1---2---4 (node 2 directly connects 3 and 4. forgive my poor way of drawing it in text) In this case, we have 11 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,2,4}, {2,3,4}, {1,2,3,4}.

From those two little examples we can see that the actual number depends on the exact structure of the tree, so, I am hoping you can help me further determine what is the factor that influences the result (I guess the maximal degree?).

Thank you!

$\endgroup$
1
$\begingroup$

Let $T$ be a tree rooted at $r$. Let the children of $r$ be $r_1,\ldots,r_\ell$, and let the corresponding subtrees be $T_1,\ldots,T_\ell$.

Consider a connected induced subgraph of $T$. There are two cases:

  • The subgraph doesn't contain $r$. In this case, the subgraph is a connected induced subgraph of some $T_i$.

  • The subgraph contains $r$. In this case, for each $i$, either the subgraph contains no vertices of $T_i$, or its intersection with $T_i$ is a connected induced subgraph of $T_i$ containing $r_i$.

Let us denote the number of subgraphs of the first type by $A(T)$, and those of the second type by $B(T)$. You are interested in $A(T) + B(T)$. The description above translates to the following recurrences: $$ \begin{align} A(T) &= \sum_{i=1}^\ell (A(T_i) + B(T_i)) \\ B(T) &= \prod_{i=1}^\ell (1 + B(T_i)) \end{align} $$ Using this, you can calculate the number of connected induced subgraphs of a tree in linear time (ignoring the cost of arithmetic).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.