- Tytuł:
- Isomorphisms and traversability of directed path graphs
- Autorzy:
-
Broersma, Hajo
Li, Xueliang - Powiązania:
- https://bibliotekanauki.pl/articles/743350.pdf
- Data publikacji:
- 2002
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
directed path graph
line digraph
isomorphism
travers-ability - Opis:
- The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pₖ(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 P₃(D) are studied, in particular with respect to isomorphism and traversability. In our main results, we characterize all digraphs D with P₃(D) ≅ D, we show that P₃(D₁) ≅ P₃(D₂) "almost always" implies D₁ ≅ D₂, and we characterize all digraphs with Eulerian or Hamiltonian P₃-graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2002, 22, 2; 215-228
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł