INTERSECTION GRAPHS OF PROPER SUBTREES OF UNICYCLIC GRAPHS

A graph is fraternally oriented iff for every three vertices u, upsilon, w the existence of the edges u --> w and upsilon --> w implies that u and v are adjacent. A directed unicyclic graph is obtained f rom a unicyclic graph by orienting the unique cycle clockwise and by orienting the appended subtrees from the cycle outwardly. Two directed subtrees s, t of a directed unicyclic graph are proper if their union contains no (directed or undirected) cycle and either they are disjoint or one of them s has its root r(s) in t and contains all the successors of r(s) in t. In the present paper we prove that G is an intersection graph of a family of proper directed subtrees of a directed unicyclic graph iff it has a fraternal orientation such that for every vertex upsilon, G(GAMMA(in)upsilon) is acyclic and G(GAMMA(out)upsilon) is the transitive closure of a tree. We describe efficient algorithms for recognizing when such graphs are perfect and for testing isomorphism of proper circular-arc graphs. (C) 1994 John Wiley & Sons, Inc.