Abstract

Abstract. If G is a graph, then its path graph, P_k(G), has vertex set identical with the set of paths of length k in G, with two vertices adjacent in P_k(G) if and only if the corresponding paths are "consecutive" in G. By diam(G) we denote the diameter of G. We study the behaviour of diam(P₂ⁱ(G)) as a function of i, where P₂ⁱ(G) is a composition P₂(P₂^i-1(G)), with P₂⁰(G))=G.

Let G be a graph. Then P₂ⁱ(G) may contain plenty of isolated vertices and at most one nontrivial component. Let us denote this component by H_i. Belan and Jurica proved

diam(G)-2<=diam(H₁)<=diam(G)+2.
We prove that for every connected graph G, up to a strictly determined collection of trees and unicyclic graphs (defined in the paper), for large i we have diam(H_i)=diam(H_i-1)+2.

We remark that the situation is analogous for line graphs and iterated line graphs. We have

diam(G)-1<=diam(L(G))<=diam(G)+1
and for every connected graph G different from a path, a cycle and a claw K_1,3, we have diam(Lⁱ(G))=diam(L^i-1(G))+1.