Given a graph of a horizontal graph as follows:

enter image description here

In such a graph, I want to efficiently (preferably a closed form) calculate the total number of graphs that can be formed with vertices x<=n (n is the total number of vertices in the original graph), such that none of the vertices in x are adjacent in the original graph.

Is there a closed form exists to calculate the same (given any n and x)?

Currently, I am literally, generating all possible combination of x vertices and then checking if any pair has an edge in the original graph. But this brute force is very expensive and does not scale. Is there a better approach?

  • $\begingroup$ This question is related to this one; I'm saying this just in case somebody answers there. $\endgroup$ – Anakhand Oct 7 '18 at 9:24

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.