<p>Given a simple undirected grap, how many induced subgraphs does it have that are not isomorphic to each other? (or in a descision version, does it have fewer than k non-isomorphic induced subgraphs).</p>

<p>Does anyone know the computational complexity of this problem? Are bounds known?</p>

CC BY-SA 3.0
2015-03-16T13:10:57.733Z
A related question seems to be: For a given n, how many graphs exists with n vertices such that no two are isomorphic.
user32149
CC BY-SA 3.0
2015-03-17T15:39:53.230Z
The number of isomorphism classes of graphs on $n$ vertices is well-studied and known asymptotically to be $2^{\binom{n}{2}}/n!$ (exact asymptotic, not big-oh). Presumably for your question you want some further restriction, e.g. induced subgraphs on $k$ vertices (where $k$ could be part of the input)? Otherwise you can always get at least $n$ non-isomorphic induced subgraphs by considering subgraphs of different numbers of vertices. Finally, do you want to consider only *connected* induced subgraphs?
Joshua Grochow
CC BY-SA 3.0
2015-03-18T14:48:45.593Z
Thanks a lot for your reply. I do not only want to consider connected induced subgraphs. In the decision version, I consider k a part of the input.
user32149
CC BY-SA 3.0
2015-03-18T16:42:36.993Z
I shouldn't have used $k$, because you already used that for the bound in the decision version. Let me try again: do you only want to consider induced subgraphs *with a given number of vertices*? If so, is the number of vertices part of the input?
Joshua Grochow
CC BY-SA 3.0
2015-03-23T10:08:47.530Z
No, I want to consider all induced subgraphs (it does not matter how many vertices they have).
user32149
<cc.complexity-theory><graph-isomorphism>
Number of non-isomorphic induced subgraphs of a graph
user32149
# Number of non-isomorphic induced subgraphs of a graph

(Asked by: username_0 on 2015-03-16)

Given a simple undirected grap, how many induced subgraphs does it have that are not isomorphic to each other? (or in a descision version, does it have fewer than k non-isomorphic induced subgraphs).

Does anyone know the computational complexity of this problem? Are bounds known?

**Tags:** cc.complexity-theory, graph-isomorphism
> **Comments:**
> **username_0**: A related question seems to be: For a given n, how many graphs exists with n vertices such that no two are isomorphic.  
> **username_1**: The number of isomorphism classes of graphs on $n$ vertices is well-studied and known asymptotically to be $2^{\binom{n}{2}}/n!$ (exact asymptotic, not big-oh). Presumably for your question you want some further restriction, e.g. induced subgraphs on $k$ vertices (where $k$ could be part of the input)? Otherwise you can always get at least $n$ non-isomorphic induced subgraphs by considering subgraphs of different numbers of vertices. Finally, do you want to consider only *connected* induced subgraphs?  
> **username_0**: Thanks a lot for your reply. I do not only want to consider connected induced subgraphs. In the decision version, I consider k a part of the input.  
> **username_1**: I shouldn't have used $k$, because you already used that for the bound in the decision version. Let me try again: do you only want to consider induced subgraphs *with a given number of vertices*? If so, is the number of vertices part of the input?  
> **username_0**: No, I want to consider all induced subgraphs (it does not matter how many vertices they have).  

---

## 0 answers

