There is a set of vertices and it is divided into $k$ independent sets. The cardinalities of these sets are following: $a_{1},a_{2},...,a_{k}$

How many non-isomorphic graphs determined on these sets are there?

I hope that someone will help me.


  • $\begingroup$ Where does this problem come from? The answer is, as far as I know, not known even for bi-partite graphs.. See for example math.stackexchange.com/questions/2321657/… $\endgroup$ – N. S. Sep 20 at 18:51
  • $\begingroup$ The question is easy if you ask for the number of different labeled such graphs, but "isomorphic" makes it very hard. $\endgroup$ – N. S. Sep 20 at 18:52
  • $\begingroup$ This MSE link treats the case of non-isomorphic bipartite graphs. $\endgroup$ – Marko Riedel Sep 21 at 14:44

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.