Intersection graphs of proper subtrees of unicyclic graphs
Fǎnicǎ Gavril · Journal of Graph Theory · 1994
Abstract A graph is fraternally oriented iff for every three vertices u, ν, w the existence of the edges u → w and ν → w implies that u and ν are adjacent. A directed unicyclic graph is obtained from 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 ν, G(Γinν) is acyclic and G(Γoutν) 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.