Abstract

Generation is constructing a complete list of a class of some combinatorial objects without isomorphs. When the objects are graphs, the problem of avoiding isomorphism tends to be difficult. The method developed to avoid isomorphic copies is one of the main criteria that determine the efficiency of a generation process. Generation by Canonical Construction Path (McKay 1998) is a general method to recursively generate combinatorial objects. In this method, larger objects, (children), are constructed out of smaller ones, (parents), through some well-defined operation, (extension), and avoiding constructing isomorphic copies at each construction step. The inverse operation of the extension is called reduction. A unique genuine reduction is defined for each graph but for the irreducible ones. An irreducible graph is one with no parent. A generated graph is accepted only if it has been extended by some extension where the inverse reduction of that extension is genuine. This approach is time and storage efficient for discarding the isomorphic copies. Based on this method, we have developed the most efficient software to generate Quartic graphs and some of its subclasses. We have also helped with the classification of subfactors of von Neumann algebra, by providing an efficient generation of Principal Graph Pairs.



Information: