𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs

✍ Scribed by L. Babel; I.N. Ponomarenko; G. Tinhofer

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
237 KB
Volume
21
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path graphs is isomorphism complete, whereas for rooted directed path graphs we present a polynomial-time isomorphism algorithm.

πŸ“œ SIMILAR VOLUMES

The Separator Theorem for Rooted Directe
The Separator Theorem for Rooted Directed Vertex Graphs
✍ B.S. Panda πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 109 KB

In this note we point out a flaw in the separator theorem for rooted directed vertex graphs due to C. L. Monma and V. K. Wei (1986, J. Combin. Theory Ser. B 41, 141 181), and present a modified separator theorem for the same class of graphs.

Characterizing directed path graphs by f
Characterizing directed path graphs by forbidden asteroids
✍ Kathie Cameron; ChΓ­nh T. HoΓ ng; Benjamin LΓ©vΓͺque πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 135 KB

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal grap

Optimal tree 3-spanners in directed path
Optimal tree 3-spanners in directed path graphs
✍ Le, HoοΏ½ng-Oanh; Le, Van Bang πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 122 KB πŸ‘ 2 views

In a graph G, a spanning tree T is called a tree t-spanner of G if the distance between any two vertices in T is at most t times their distance in G. While the complexity of finding a tree t-spanner of a given graph is known for any fixed t 3, the case t Ο­ 3 still remains open. In this article, we s

The degree-preserving spanning tree prob
The degree-preserving spanning tree problem in strongly chordal and directed path graphs
✍ Ching-Chi Lin; Gerard J. Chang; Gen-Huey Chen πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 108 KB

## Abstract Suppose __G__ is a connected graph and __T__ a spanning tree of __G__. A vertex __v__ Ξ΅ __V__(__G__) is said to be a degree‐preserving vertex if its degree in __T__ is the same as its degree in __G__. The degree‐preserving spanning tree problem is to find a spanning tree __T__ of a conn