ENUMERATION OF DIFFERENCE GRAPHS

A difference graph is a bipartite graph G = (X, Y; E) such that all th e neighborhoods of the vertices of X are comparable by inclusion. We e numerate labeled and unlabeled difference graphs with or without a bip artition of the vertices into two stable sets. The labeled enumeration s are expressed in terms of combinatorial numbers related to the Stirl ing numbers of the second kind.