Back to University of Twente portal
Isomorphisms and traversability of directed path graphs
Broersma, H.J. and Li , X. (1998) Isomorphisms and traversability of directed path graphs. [Report]
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 161Kb |
| Abstract: | 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) D1 �= D2, and we characterize all digraphs with Eulerian or Hamiltonian !P3-graphs. |
| Item Type: | Report |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/30617 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 141258