Counting graphs with a duality property

Summary

Abstract

The enumeration of graphs and other structures satisfying a duality condition, such as self-complementarity, is surveyedo A modification of Burnside's lemma due to de Bruijn is presented in order to unify and simplify the treatment of such problems. Some new equalities between classes of graphs and digraphs are found which seem not to be explained by natural 1-1 correspondences. Also some new natural 1–1 correspondences are derived using the modified Burnside lemma. Asymptotic analyses of the exact numbers are reviewed, and some recent results described.

Introduction

Methods for counting graphs and related structures which satisfy a duality condition are well-established in the literature. A duality condition is defined by invariance up to isomorphism under some operation. Complementation is an operation which has often been considered. Self-complementary structures enumerated include graphs and digraphs [Re63], tournaments [Sr70], n-plexes [Pa73a], m-ary relations [Wi74], multigraphs [Wi78], eulerian graphs [Ro69], bipartite graphs [Qu79], sets [B59 and B64], and boolean functions [Ni59, El60, Ha63, Ha64, and PaR-A]. Closely related are 2-colored or signed structures invariant under color interchange or sign interchange. These take in 2-colored graphs [HP63 and Ha7 9], graphs in which points, lines, or points and lines are signed [HPRS77], signed graphs under weak isomorphism [So80], 2-colored polyhedra [R27 and KnPR75], and necklaces [PS77 and Mi78]. The converse of a digraph results when all orientations of arcs are reversed.