Counting acyclic orderings in directed acyclic graphs

Joseph Fox1, Aimee Judd1
1Aquinas College 1700 E Fulton St, Grand Rapids, MI 49506

Abstract

An acyclic ordering of a directed acyclic graph (DAG) \( G \) is a sequence \( \alpha \) of the vertices of \( G \) with the property that if \( i < j \), then there is a path in \( G \) from \( \alpha(i) \) to \( \alpha(j) \). In this paper, we explore the problem of finding the number of possible acyclic orderings of a general DAG. The main result is a method for reducing a general DAG to a simpler one when counting the number of acyclic orderings. Along the way, we develop a formula for quickly obtaining this count when a DAG is a tree.

Keywords: https://combinatorialpress.com/article/jcmcc/Volume%20115/Counting%20Acyclic%20Orderings%20in%20Directed%20Acyclic%20Graphs.PDF