1
$\begingroup$

I am trying to make a list of all subgraphs up to isomorphism of $K_n$. (Not of all the $2^{\tbinom{n}{2}}$ subgraphs; only up to isomorphism.) I have two questions:

  1. Is there a formula which will tell me how many subgraphs are there for a given n? If no general formula exists are there specific answers for $n<20$, and what are they.

  2. If I want to make a list of subgraphs which avoids the complement of any subgraph (of $K_n$ up to isomorphism) already in the list, and is maximal possible, how do I do that? Can someone suggest an algorithmic way to do this. I plan to write a computer program to generate this list.

Thanks.

  • 0
    Note that any subgraph of $K_{n+1}$ that does not have all $n+1$ vertices is a subgraph of $K_n$. So you really only need to count the ones that *do* involve all vertices; symmetry should help a lot there.2011-06-23

1 Answers 1

2

So you want the number of graphs (up to isomorphism) on $n$ vertices or fewer. There is no simple formula known, just estimates. As Arturo suggests, see the OEIS, it will probably point to to some estimates.

To avoid complements, in the first place only list graphs with fewer than half the available edges. The tricky part is when you get to graphs that have exactly half the available edges - there are such things as self-complementary graphs. For example, the complement of a 5-cycle in $K_5$ is again (isomorphic to) a 5-cycle. Making sure you only count one in each such pair, all I can think of is testing for isomorphism (which you're going to have to do anyway, if you really want to list the graphs and not just count them). Graph isomorphism is believed to be an intractably hard problem, but for $n\le20$ I'm sure everything has been tabulated, and once again OEIS is your friend.

  • 0
    Yes, that sequence starts with $n=0$. There is, by convention, one graph on zero vertices, the empty graph. Then one graph on one vertex, two on two, four on three, and off you go.2011-06-23