Number of Directed Acyclic Graphs with Extra Constraints

Abstract

This report investigates the enumeration of labeled directed acyclic graphs (DAGs) under various structural constraints, extending an inclusion–exclusion recurrence introduced by R.W. Robinson. Starting from the enumeration of general DAGs via out-point partitioning, the recursive method is adapted to count more specialized classes such as DAGs with a fixed number of arcs or out-points. The Robinson method is also applied to create a formula for the enumeration of rooted directed trees, polytrees, and a special triangle structure. For each of these constrained graph classes, both the closed-form expressions and the derived recursive enumeration formulas are explained, showcasing the versatility and mathematical elegance of Robinson’s technique. A main focus of this report is the derivation and interpretation of the Robinson recurrence that adjusts the choose-attach model while using the local attachment rules. This report also presents visual illustrations of the original Robinson method and its adaptations. The results of these formulas are shown in graphs and tables to show the exponential growth of each class. The results bring together several enumeration problems in graph theory under a single recursive framework, offering both theoretical insight and practical enumeration formulas. The contributions of this thesis provide an analysis of DAG enumeration problems, bridging theoretical insights and practical relevance. These results have important implications for a wide range of applications, including Bayesian networks, causal inference modeling, scheduling, and network design. Finally, promising directions for future research are mentioned, emphasizing potential extensions to more complex graph structures and advanced enumeration methodologies.