Convergent sequences of iterated H-line graphs Original Research Article

For a connected graph H of order at least 3, the H-line graph HL(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of HL(G) are adjacent if and only if the corresponding edges of G are adjacent and belong to a common copy of H. For k ⩾ 2, the kth iterated H-line graph HLk(G) is defined as HL(HLk−1(G)), where HL1(G) = HL(G) and HLk−1(G) is assumed to be nonempty. A sequence {Gk} of graphs is said to converge to a graph G if there exists a positive integer N such that Gk ≅ G for every integer k ⩾ N. If the sequence {Gk} is finite, it is said to terminate. If {Gk} neither converges nor terminates, then the sequence diverges. We present necessary conditions for {HLk(G)} to converge to a connected limit graph and sufficient conditions for the sequence {HLk(G)} to diverge. When H is P4, P5, or K1,n, n ⩾ 3, we characterize those graphs G for which the sequence {HLk(G)} converges.