Isomorphisms and traversability of directed path graphs

Haitze J. Broersma, Xueliang Li, X. Li

Research output: Book/ReportReportProfessional

74 Downloads (Pure)

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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages12
Publication statusPublished - 1998

Publication series

NameMemorandum Faculteit TW
PublisherUniversity of Twente
No.1433

Keywords

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

Cite this