Skip to main content
added 61 characters in body
Source Link
zack
  • 206
  • 1
  • 6

Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc.

For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)?

For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc.

For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

deleted 60 characters in body; edited tags; edited title
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

Upper bound on the number of subgraphs in a connected acyclic graphtree

I was wondering ifIs there is any reference or results on thean upper bound of the number of induced subgraphs in a connected acyclic graph (not directed)tree (i.e., treeconnected acyclic undirected graph).?

For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

Thanks!

Upper bound on the number of subgraphs in a connected acyclic graph

I was wondering if there is any reference or results on the upper bound of the number of induced subgraphs in a connected acyclic graph (not directed) (i.e., tree). For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

Thanks!

Upper bound on the number of subgraphs in a tree

Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)?

For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

added 11 characters in body
Source Link
zack
  • 206
  • 1
  • 6

I was wondering if there is any reference or results on the upper bound of the number of connectedinduced subgraphs in a connected acyclic graph (not directed) (i.e., tree). For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

Thanks!

I was wondering if there is any reference or results on the upper bound of the number of connected subgraphs in a connected acyclic graph (not directed). For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

Thanks!

I was wondering if there is any reference or results on the upper bound of the number of induced subgraphs in a connected acyclic graph (not directed) (i.e., tree). For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

Thanks!

added 10 characters in body
Source Link
zack
  • 206
  • 1
  • 6
Loading
Source Link
zack
  • 206
  • 1
  • 6
Loading