Intersection graphs on concatenable subtrees of graphs

Intersection graphs on concatenable subtrees of graphs

0.00 Avg rating0 Votes
Article ID: iaor19951084
Country: Netherlands
Volume: 52
Issue: 2
Start Page Number: 195
End Page Number: 209
Publication Date: Aug 1994
Journal: Discrete Applied Mathematics
Authors: ,
Abstract:

A graph is fraternally oriented if for every three vertices u,v,w the existence of the edges u⇒w and v⇒w implies that u and v are adjacent. An acanthus is a graph which is a free tree or is obtained by adding an edge to a free tree. Two rooted subtrees of an undirected graph are called concatenable if either they are disjoint or their intersection contains the root of one of them and their union contains no cycle. The authors prove that a connected graph G is the intersection graph of a family of pairwise concatenable edge subtrees of an undirected graph if and only if it is the intersection graph of a family of pairwise concatenable edge subtrees of an acanthus if and only if G has a fraternal orientation such that for every vertex v the subgraphs G(¦)inv) and G(¦)outv) have no directed cycles.

Reviews

Required fields are marked *. Your email address will not be published.