The Partition Theorem of Connected Digraphs and Its Enumerative Applications

Abstract

The partition theorem of connected graphs was established in \(1985\) and it is very useful in graphical enumeration. In this paper, we generalize th partition theorem from connected graphs to weakly connected digraphs. Applying these two partition theorems, we obtain the recursive formulas for enumerations of labeled connected (even) digraphs, labeled rooted connected (even) digraphs whose roots have a given number of blocks, and labeled connected \(d\)-cyclic (\(d \geq 0\)) (directed) graphs, etc. Moreover, a new proof of the counting formula for labeled trees (Cayley formula) is given.