Given a graph of a horizontal graph as follows:
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?