DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

PDF

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

ISOMORPHISMS AND TRAVERSABILITY OF DIRECTED PATH GRAPHS

Hajo Broersma

Faculty of Mathematical Sciences
University of Twente
P.O. Box 217, 7500 AE Enschede, The Netherlands
e-mail: broersma@math.utwente.nl

 Xueliang Li

Center for Combinatorics
Nankai University
Tianjin 300071, P.R. China
e-mail: x.li@eyou.com

Abstract

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.

References

[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

Close