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 !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.
Item Type:Report
Additional information:Memorandum Faculteit TW, nr 1433
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