DMGT

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

CONNECTIVITY OF PATH GRAPHS

Martin Knor

Slovak University of Technology
Faculty of Civil Engineering, Department of Mathematics
Radlinského 11, 813 68 Bratislava, Slovakia
e-mail: knor@vox.svf.stuba.sk

L'udoví t Niepel

Kuwait University, Faculty of Science
Department of Mathematics & Computer Science
P.O. box 5969 Safat 13060, Kuwait
e-mail: NIEPEL@MATH-1.sci.kuniv.edu.kw.

Abstract

We prove a necessary and sufficient condition under which a connected graph has a connected P₃-path graph. Moreover, an analogous condition for connectivity of the P_k-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.

References

[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 P₄-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