# Number of non-isomorphic induced subgraphs of a graph

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?

• A related question seems to be: For a given n, how many graphs exists with n vertices such that no two are isomorphic. – user32149 Mar 16 '15 at 13:10
• 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 Mar 17 '15 at 15:39
• 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 Mar 18 '15 at 14:48
• 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 Mar 18 '15 at 16:42
• No, I want to consider all induced subgraphs (it does not matter how many vertices they have). – user32149 Mar 23 '15 at 10:08