### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 12 |

Publication status | Published - 1998 |

### Publication series

Name | Memorandum Faculteit TW |
---|---|

Publisher | University of Twente |

No. | 1433 |

### Keywords

- MSC-05C05
- MSC-05C45
- METIS-141258
- MSC-05C75
- IR-30617
- EWI-3253

### Cite this

*Isomorphisms and traversability of directed path graphs*. (Memorandum Faculteit TW; No. 1433). Enschede: University of Twente, Department of Applied Mathematics.

}

*Isomorphisms and traversability of directed path graphs*. Memorandum Faculteit TW, no. 1433, University of Twente, Department of Applied Mathematics, Enschede.

**Isomorphisms and traversability of directed path graphs.** / Broersma, Haitze J.; Li, Xueliang; Li, X.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - Isomorphisms and traversability of directed path graphs

AU - Broersma, Haitze J.

AU - Li, Xueliang

AU - Li, X.

N1 - Imported from MEMORANDA

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - MSC-05C05

KW - MSC-05C45

KW - METIS-141258

KW - MSC-05C75

KW - IR-30617

KW - EWI-3253

M3 - Report

T3 - Memorandum Faculteit TW

BT - Isomorphisms and traversability of directed path graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -