Diameter of path graphs
Hannah Chung, Daniela Ferrero, Alan Taylor, Jeremy T. Warshauer · Journal of Discrete Mathematical Sciences and Cryptography · 2004
For a given graph G and a positive integer k the k -path graph, Pk (G), has for vertices the set of all paths of length k in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length k – 1 in G, and their union forms either a cycle or a path of length k + 1 in G. Path graphs were proposed as an extension of line graphs. Indeed, P 1(G) coincides with the line graph of G. The diameter of line graphs and 2-path graphs have been previously studied and more generally, some bounds have presented in the case k ≤ 5. In this paper we present upper bounds for the diameter of iterated k -path graphs for any positive integer k, which improve the known upper bounds.