Enumeration of Unlabeled Directed Hypergraphs

Jianguo Qian

Abstract


We consider the enumeration of unlabeled directed hypergraphs by using Pólya's counting theory and Burnside's counting lemma. Instead of characterizing the cycle index of the permutation group acting on the hyperarc set $A$, we treat each cycle in the disjoint cycle decomposition of a permutation $\rho$ acting on $A$ as an equivalence class (or orbit) of $A$ under the operation of the group generated by $\rho$. Compared to the cycle index method, our approach is  more effective in  dealing with the enumeration of directed hypergraphs. We deduce the explicit counting formulae for the unlabeled $q$-uniform and unlabeled general directed hypergraphs. The former generalizes the well known result for 2-uniform directed hypergraphs, i.e., for the ordinary directed graphs introduced by Harary and Palmer.


Keywords


unlabeled directed hypergraph; uniform; enumeration

Full Text: PDF