ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

DOI 10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2017: 0.601

SCImago Journal Rank (SJR) 2017: 0.633

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 22(2) (2002) 215-228
DOI: 10.7151/dmgt.1170


Hajo Broersma

Faculty of Mathematical Sciences
University of Twente
P.O. Box 217, 7500 AE Enschede, The Netherlands

Xueliang Li

Center for Combinatorics
Nankai University
Tianjin 300071, P.R. China


The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pk(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 P3(D) are studied, in particular with respect to isomorphism and traversability. In our main results, we characterize all digraphs D with P3(D) ≅ D, we show that P3(D1) ≅ P3(D2) "almost always'' implies D1 ≅ D2, and we characterize all digraphs with Eulerian or Hamiltonian P3-graphs.

Keywords: directed path graph, line digraph, isomorphism, travers-ability.

2000 Mathematics Subject Classification: 05C75, 05C45, 05C05.


[1] R.E.L. Aldred, M.N. Ellingham, R.L. Hemminger and P. Jipsen, P3-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.
[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 P3-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.

Received 23 February 1998
Revised 18 January 2002