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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.