Geodesic
Isomorphisms and traversability of directed path graphs
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 2, pp. 215-228.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: directed path graph, line digraph, isomorphism, travers-ability 
@article{DMGT_2002_22_2_a0,
     author = {Broersma, Hajo and Li, Xueliang},
     title = {Isomorphisms and traversability of directed path graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {215--228},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a0/}
}
TY  - JOUR
AU  - Broersma, Hajo
AU  - Li, Xueliang
TI  - Isomorphisms and traversability of directed path graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2002
SP  - 215
EP  - 228
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a0/
LA  - en
ID  - DMGT_2002_22_2_a0
ER  - 
%0 Journal Article
%A Broersma, Hajo
%A Li, Xueliang
%T Isomorphisms and traversability of directed path graphs
%J Discussiones Mathematicae. Graph Theory
%D 2002
%P 215-228
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a0/
%G en
%F DMGT_2002_22_2_a0
Broersma, Hajo; Li, Xueliang. Isomorphisms and traversability of directed path graphs. Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 2, pp. 215-228. http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a0/

[1] R.E.L. Aldred, M.N. Ellingham, R.L. Hemminger and P. Jipsen, P₃-isomorphisms for graphs, J. Graph Theory 26 (1997) 35-51, doi: 10.1002/(SICI)1097-0118(199709)26:135::AID-JGT5>3.0.CO;2-I

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan/Elsevier, London/New York, 1976).

[3] H.J. Broersma and C. Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444, doi: 10.1002/jgt.3190130406.

[4] F. Harary and R.Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo 9 (2) (1960) 161-168, doi: 10.1007/BF02854581.

[5] R.L. Hemminger and L.W. Beineke, Line graphs and line digraphs, in: L.W. Beineke and R.J. Wilson, eds, Selected Topics in Graph Theory (Academic Press, London, New York, San Francisco, 1978).

[6] X. Li, Isomorphisms of P₃-graphs, J. Graph Theory 21 (1996) 81-85, doi: 10.1002/(SICI)1097-0118(199601)21:181::AID-JGT11>3.0.CO;2-V