Isomorphisms and traversability of directed path graphs

Hajo Broersma, Xueliang Li

Research output: Contribution to journalArticleAcademicpeer-review

95 Downloads (Pure)


The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pk(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 P3(D) are studied, in particular with respect to isomorphism and traversability. In our main results, we characterize all digraphs D with P3(D) ≅ D, we show that P3(D1) ≅ P3(D2) "almost always'' implies D1 ≅ D2, and we characterize all digraphs with Eulerian or Hamiltonian P3-graphs.
Original languageEnglish
Pages (from-to)215-228
Number of pages16
JournalDiscussiones mathematicae. Graph theory
Issue number2
Publication statusPublished - 2002


Dive into the research topics of 'Isomorphisms and traversability of directed path graphs'. Together they form a unique fingerprint.

Cite this