Download PDF - Connectivity of path graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Connectivity of path graphs

Authors 1, 2

Affiliations

  1. Slovak University of Technology, Faculty of Civil Engineering, Department of Mathematics, Radlinského 11, 813 68 Bratislava, Slovakia
  2. Kuwait University, Faculty of Science, Department of Mathematics & Computer Science, P.O. box 5969 Safat 13060, Kuwait

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ₖ-path graph of a connected graph which does not contain a cycle of length smaller than k+1 is derived.

Keywords

ENG
connectivity, path graph, cycle

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2000/20/2
Export to PBN, Opens in new tab
Pages:
181-195
Main language of publication
English
Received
1999-07-20
Accepted
2000-03-20
Published
2000

DOI: 10.7151/dmgt.1118

Exact and natural sciences