# How many induced subgraphs does $G$ have of specific size

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.

• 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
Commented Mar 24, 2014 at 7:33
• I am looking for max possible number of subgraphs. Actually number of edges I have is $kn-\frac{k(k+1)}{2}=O(nk)$. Commented Mar 24, 2014 at 8:21
• 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? Commented Mar 24, 2014 at 9:01

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.
Björklund et al. (2012) 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)$.