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ₖ-path graph of a connected graph which does not contain a cycle of length smaller than k+1 is derived.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1118,
author = {Martin Knor and L'udov\'\i t Niepel},
title = {Connectivity of path graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {20},
year = {2000},
pages = {181-195},
zbl = {0984.05050},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1118}
}
Martin Knor; L'udovít Niepel. Connectivity of path graphs. Discussiones Mathematicae Graph Theory, Tome 20 (2000) pp. 181-195. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1118/
[000] [1] A. Belan and P. Jurica, Diameter in path graphs, Acta Math. Univ. Comenian. LXVIII (1999) 111-126. | Zbl 0929.05024
[001] [2] H.J. Broersma and C. Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444, doi: 10.1002/jgt.3190130406. | Zbl 0677.05068
[002] [3] M. Knor and L'. Niepel, Path, trail and walk graphs, Acta Math. Univ. Comenian. LXVIII (1999) 253-256. | Zbl 0942.05033
[003] [4] M. Knor and L'. Niepel, Distances in iterated path graphs, Discrete Math. (to appear).
[004] [5] M. Knor and L'. Niepel, Centers in path graphs, (submitted).
[005] [6] M. Knor and L'. Niepel, Graphs isomorphic to their path graphs, (submitted).
[006] [7] H. Li and Y. Lin, On the characterization of path graphs, J. Graph Theory 17 (1993) 463-466, doi: 10.1002/jgt.3190170403. | Zbl 0780.05048
[007] [8] X. Li and B. Zhao, Isomorphisms of P₄-graphs, Australasian J. Combin. 15 (1997) 135-143. | Zbl 0878.05061
[008] [9] X. Yu, Trees and unicyclic graphs with Hamiltonian path graphs, J. Graph Theory 14 (1990) 705-708, doi: 10.1002/jgt.3190140610. | Zbl 0743.05018