Enumerating Labeled and Unlabeled Graphs

We begin with the enumeration of labeled graphs because, as with counting, they are easier to deal with. The algorithm we outline next for enumerating labeled graphs we will use and modify to enumerate unlabeled graphs. 

The orderly algorithm is to enumeration what Polya s theorem is to counting. Orderly generation is generally attributed to Read, ° although 

One issue we have not yet addressed with orderly generation is computational complexity. Although orderly generation is certainly faster than labeled enumeration followed by a removal of the duplicated structures, is it the optimum solution First we have to ask what optimum means when 

As far as general graphs are concerned, some codes are available for their enumeration. In particular, two codes to enumerate small graphs and bipartite graphs can be downloaded along with Nauty, a graph canonizer we mentioned earlier.  

The -tuple technique has lead to numerous implementations and extensions. In particular. Contras et al. extended the w-tuple enumeration algorithm 

---