Enumeration of vacuously transitive relations

AbstractThe concept of vacuously transitive relation is defined and under an appropriate isomorphism, the equivalence classes of such relations are enumerated by use of the power group enumeration theorem [3]. This enumeration is shown to be combinatorially equivalent to a counting series derived by Harary and Prins [4] for certain kinds of bicolored graphs. Finally, it is shown that the main result can be extended to cover two additional cases of interest