ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 20(2) (2000) 181-195
DOI: 10.7151/dmgt.1118


Martin Knor

Slovak University of Technology
Faculty of Civil Engineering, Department of Mathematics
Radlinského 11, 813 68 Bratislava, Slovakia

L'udoví t Niepel

Kuwait University, Faculty of Science
Department of Mathematics & Computer Science
P.O. box 5969 Safat 13060, Kuwait


We prove a necessary and sufficient condition under which a connected graph has a connected P3-path graph. Moreover, an analogous condition for connectivity of the Pk-path graph of a connected graph which does not contain a cycle of length smaller than k+1 is derived.

Keywords: connectivity, path graph, cycle.

2000 Mathematics Subject Classification: 05C40, 05C38.


[1] A. Belan and P. Jurica, Diameter in path graphs, Acta Math. Univ. Comenian. LXVIII (1999) 111-126.
[2] H.J. Broersma and C. Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444, doi: 10.1002/jgt.3190130406.
[3] M. Knor and L'. Niepel, Path, trail and walk graphs, Acta Math. Univ. Comenian. LXVIII (1999) 253-256.
[4] M. Knor and L'. Niepel, Distances in iterated path graphs, Discrete Math. (to appear).
[5] M. Knor and L'. Niepel, Centers in path graphs, (submitted).
[6] M. Knor and L'. Niepel, Graphs isomorphic to their path graphs, (submitted).
[7] H. Li and Y. Lin, On the characterization of path graphs, J. Graph Theory 17 (1993) 463-466, doi: 10.1002/jgt.3190170403.
[8] X. Li and B. Zhao, Isomorphisms of P4-graphs, Australasian J. Combin. 15 (1997) 135-143.
[9] X. Yu, Trees and unicyclic graphs with Hamiltonian path graphs, J. Graph Theory 14 (1990) 705-708, doi: 10.1002/jgt.3190140610.

Received 20 July 1999
Revised 20 March 2000