Set graphs. I. Hereditarily finite sets and extensional acyclic orientations

A graph G is said to be a set graph if it admits an acyclic orientation which is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set. In this paper, we initiate the study of set graphs. On the one hand, we identify several necessary conditions that every set graph must satisfy. On the other hand, we show that set graphs form a rich class of graphs containing all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation. Inspired by manipulations of hereditarily finite sets, we give simple proofs of two well-known results about claw-free graphs. We give a complete characterization of unicyclic set graphs, and point out two NP-complete problems closely related to the problem of recognizing set graphs. Finally, we argue that these three problems are solvable in linear time on graphs of bounded treewidth. (C) 2011 Elsevier B.V. All rights reserved.