Isomorphisms and traversability of directed path graphs

Haitze J. Broersma, Xueliang Li, X. Li

Research output: Book/ReportReportProfessional

43 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

Broersma, H. J., Li, X., & Li, X. (1998). Isomorphisms and traversability of directed path graphs. (Memorandum Faculteit TW; No. 1433). Enschede: University of Twente, Department of Applied Mathematics.
Broersma, Haitze J. ; Li, Xueliang ; Li, X. / Isomorphisms and traversability of directed path graphs. Enschede : University of Twente, Department of Applied Mathematics, 1998. 12 p. (Memorandum Faculteit TW; 1433).
@book{9e0be6454760404987a1c9c6bb6a2fe1,
title = "Isomorphisms and traversability of directed path graphs",
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.",
keywords = "MSC-05C05, MSC-05C45, METIS-141258, MSC-05C75, IR-30617, EWI-3253",
author = "Broersma, {Haitze J.} and Xueliang Li and X. Li",
note = "Imported from MEMORANDA",
year = "1998",
language = "Undefined",
series = "Memorandum Faculteit TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1433",

}

Broersma, HJ, Li, X & Li, X 1998, 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.

Enschede : University of Twente, Department of Applied Mathematics, 1998. 12 p. (Memorandum Faculteit TW; No. 1433).

Research output: Book/ReportReportProfessional

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 -

Broersma HJ, Li X, Li X. Isomorphisms and traversability of directed path graphs. Enschede: University of Twente, Department of Applied Mathematics, 1998. 12 p. (Memorandum Faculteit TW; 1433).