Isomorphisms and traversability of directed path graphs

Hajo Broersma, and Xueliang Li. "Isomorphisms and traversability of directed path graphs." Discussiones Mathematicae Graph Theory 22.2 (2002): 215-228. <http://eudml.org/doc/270627>.

@article{HajoBroersma2002,
abstract = {The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pₖ(D) of a digraph D is obtained by representing the directed paths on k vertices of D by vertices. Two vertices are joined by an arc whenever the corresponding directed paths in D form a directed path on k+1 vertices or form a directed cycle on k vertices in D. In this introductory paper several properties of P₃(D) are studied, in particular with respect to isomorphism and traversability. In our main results, we characterize all digraphs D with P₃(D) ≅ D, we show that P₃(D₁) ≅ P₃(D₂) "almost always" implies D₁ ≅ D₂, and we characterize all digraphs with Eulerian or Hamiltonian P₃-graphs.},
author = {Hajo Broersma, Xueliang Li},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {directed path graph; line digraph; isomorphism; travers-ability; traversability; Euler graph; Hamilton graph},
language = {eng},
number = {2},
pages = {215-228},
title = {Isomorphisms and traversability of directed path graphs},
url = {http://eudml.org/doc/270627},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Hajo Broersma
AU - Xueliang Li
TI - Isomorphisms and traversability of directed path graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 2
SP - 215
EP - 228
AB - The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pₖ(D) of a digraph D is obtained by representing the directed paths on k vertices of D by vertices. Two vertices are joined by an arc whenever the corresponding directed paths in D form a directed path on k+1 vertices or form a directed cycle on k vertices in D. In this introductory paper several properties of P₃(D) are studied, in particular with respect to isomorphism and traversability. In our main results, we characterize all digraphs D with P₃(D) ≅ D, we show that P₃(D₁) ≅ P₃(D₂) "almost always" implies D₁ ≅ D₂, and we characterize all digraphs with Eulerian or Hamiltonian P₃-graphs.
LA - eng
KW - directed path graph; line digraph; isomorphism; travers-ability; traversability; Euler graph; Hamilton graph
UR - http://eudml.org/doc/270627
ER -