On The Enumeration of The Transitive and Acyclic Digraphs Having a Fixed Support Set

Abstract

In previous works of the author, the concept of a binary reflexive adjacency relations was introduced on the set of all binary relations of the set , and an algebraic system consisting of all binary relations of the set  and of all unordered pairs of adjacent binary relations was defined. If  is a finite set, then this algebraic system is a graph (graph of binary relations ). The current paper introduces the notion of a support set for acyclic and transitive digraphs. This is the collections and  consisting of the vertices of the digraph  that have zero indegree and zero outdegree, respectively. It is proved that if  is a connected component of the graph  containing the acyclic or transitive digraph , then . A formula for the number of acyclic and  transitive digraphs having a fixed support set is obtained.