<p>Consider a star graph, if we take a center of star union with $l-1$ arbitrary vertices then the corresponding subgraph is induced connected subgraph. So the maximum number is about $n-1\choose l-1$. We can extend this class of graphs by connecting arbitrary vertices together to have more edges. It's also possible to achieve closer to $n \choose l$ if $l$ is much smaller than $k$, or $k$ is big enough.</p>

CC BY-SA 3.0
2014-03-24T09:32:40.293Z
2014-03-25T13:32:30.393Z
2014-03-25T13:32:30.393Z
Saeed
<p>This does not completely answer your question. I don't believe any upper bounds are known with respect to the average degree of a graph, but here is a result about graphs where the maximum degree is bounded.</p>

<p><a href="http://doi.acm.org/10.1145/2151171.2151181" rel="nofollow">Björklund et al. (2012)</a> showed that the number of connected vertex subsets of a graph with $n$ vertices and maximum degree $d$ is at most $(2^{d+1}-1)^{n/(d+1)}+n$.</p>

<p>For maximum degrees 3,4, and 5, this gives the upper bounds $O(1.9680^n)$, $O(1.9874^n)$, and $O(1.9948^n)$.</p>

CC BY-SA 3.0
2014-03-24T09:13:02.010Z
2014-03-24T09:13:02.010Z
Serge Gaspers
<p>Let $G$ be a connected graph with $n$ vertices and $O(nk)$ edges, ($k$ is parameter). 
Then how many connected induced subgraphs of size $l$  does $G$ have?   </p>

<p>The simple case when $l=2$, The number of subgraphs is number of edges which is $O(nk)$. How can we generalize this one. </p>

CC BY-SA 3.0
2014-03-24T07:33:20.743Z
It is hard to tell whether you are asking for the max possible number (over all graphs on n vertices and kn edges) or whether you mean an expected number, or something else. If you do mean expected or average number, then you need to mention the distribution of graphs in consideration.
JimN
CC BY-SA 3.0
2014-03-24T08:21:44.287Z
I am looking for max possible number of subgraphs. 
Actually number of edges I have is $kn-\frac{k(k+1)}{2}=O(nk)$.
Kumar
CC BY-SA 3.0
2014-03-24T09:01:28.630Z
I think it would help if you state the entity that you want to count more formally inside the question. And are we counting up to isomorphism or not?
Kaveh
<graph-theory>
How many induced subgraphs does $G$ have of specific size
Kumar
# How many induced subgraphs does $G$ have of specific size

(Asked by: username_0 on 2014-03-24)

Let $G$ be a connected graph with $n$ vertices and $O(nk)$ edges, ($k$ is parameter).
Then how many connected induced subgraphs of size $l$ does $G$ have?

The simple case when $l=2$, The number of subgraphs is number of edges which is $O(nk)$. How can we generalize this one.

**Tags:** graph-theory
> **Comments:**
> **username_1**: It is hard to tell whether you are asking for the max possible number (over all graphs on n vertices and kn edges) or whether you mean an expected number, or something else. If you do mean expected or average number, then you need to mention the distribution of graphs in consideration.  
> **username_0**: I am looking for max possible number of subgraphs.  Actually number of edges I have is $kn-\frac{k(k+1)}{2}=O(nk)$.  
> **username_2**: I think it would help if you state the entity that you want to count more formally inside the question. And are we counting up to isomorphism or not?  

---

## 2 answers

### Answer by username_3 on 2014-03-24. Score: 5 | Accepted answer

Consider a star graph, if we take a center of star union with $l-1$ arbitrary vertices then the corresponding subgraph is induced connected subgraph. So the maximum number is about $n-1\choose l-1$. We can extend this class of graphs by connecting arbitrary vertices together to have more edges. It's also possible to achieve closer to $n \choose l$ if $l$ is much smaller than $k$, or $k$ is big enough.


---

### Answer by username_4 on 2014-03-24. Score: 3

This does not completely answer your question. I don't believe any upper bounds are known with respect to the average degree of a graph, but here is a result about graphs where the maximum degree is bounded.

[Björklund et al. (2012)](http://doi.acm.org/10.1145/2151171.2151181) showed that the number of connected vertex subsets of a graph with $n$ vertices and maximum degree $d$ is at most $(2^{d+1}-1)^{n/(d+1)}+n$.

For maximum degrees 3,4, and 5, this gives the upper bounds $O(1.9680^n)$, $O(1.9874^n)$, and $O(1.9948^n)$.


---

