# Isomorphisms and traversability of directed path graphs

Discussiones Mathematicae Graph Theory (2002)

- Volume: 22, Issue: 2, page 215-228
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHajo Broersma, and Xueliang Li. "Isomorphisms and traversability of directed path graphs." Discussiones Mathematicae Graph Theory 22.2 (2002): 215-228. <http://eudml.org/doc/270627>.

@article{HajoBroersma2002,

abstract = {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.},

author = {Hajo Broersma, Xueliang Li},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {directed path graph; line digraph; isomorphism; travers-ability; traversability; Euler graph; Hamilton graph},

language = {eng},

number = {2},

pages = {215-228},

title = {Isomorphisms and traversability of directed path graphs},

url = {http://eudml.org/doc/270627},

volume = {22},

year = {2002},

}

TY - JOUR

AU - Hajo Broersma

AU - Xueliang Li

TI - Isomorphisms and traversability of directed path graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2002

VL - 22

IS - 2

SP - 215

EP - 228

AB - 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.

LA - eng

KW - directed path graph; line digraph; isomorphism; travers-ability; traversability; Euler graph; Hamilton graph

UR - http://eudml.org/doc/270627

ER -

## References

top- [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:1<35::AID-JGT5>3.0.CO;2-I Zbl0884.05065
- [2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan/Elsevier, London/New York, 1976). Zbl1226.05083
- [3] H.J. Broersma and C. Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444, doi: 10.1002/jgt.3190130406. Zbl0677.05068
- [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. Zbl0099.18205
- [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). Zbl0434.05056
- [6] X. Li, Isomorphisms of P₃-graphs, J. Graph Theory 21 (1996) 81-85, doi: 10.1002/(SICI)1097-0118(199601)21:1<81::AID-JGT11>3.0.CO;2-V Zbl0841.05071

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.