Isomorphisms and traversability of directed path graphs


Broersma, H.J. and Li , X. (1998) Isomorphisms and traversability of directed path graphs. [Report]

open access
Abstract:The concept of a line digraph is generalized to that of a directed path graph. The directed path graph $\forw P_k(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 $\forw P_3(D)$ are studied, in particular with respect to isomorphism and traversability. In our main results, we characterize all digraphs $D$ with $\forw P_3(D)\cong D$, we show that $\forw P_3(D_1)\cong\forw P_3(D_2)$ ``almost always'' implies $D_1\cong D_2$, and we characterize all digraphs with Eulerian or Hamiltonian $\forw P_3$-graphs.
Item Type:Report
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 141258