On the number of deadlock graphs

The deadlock detection problem for serially-reusable, single-unit, single-request resources is equivalent to cycle detection in a bipartite graph. A bipartite graph containing exactly one cycle represents a single deadlock. There are many algorithms to detect a deadlock. In this paper, we derive two formulas to determine the exact number of deadlock and non-deadlock graphs which are necessary to determine the complexity of a deadlock detection algorithm.