Enumeration of unlabeled directed hypergraphs

Jianguo Qian¹

¹Xiamen University

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

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.

Détail

DOI : 10.37236/2766

Classification : 05C30, 05C65, 05C20
Mots-clés : unlabeled directed hypergraph, uniform, enumeration