Convergent sequences of iterated H-line graphs

✍ Scribed by Gary Chartrand; Heather Gavlas; Michelle Schultz

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 629 KB
• Volume: 147
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00258-k

✦ Synopsis

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-I(G)), where HL1(G) = HL(G) and HL k-I(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 G k ~-G for every integer k >~ N. If the sequence { G k } is finite, it is said to terminate. If { G k } 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 { HL~(G)} to diverge. When H is P4, Ps, or KI,,, n >~ 3, we characterize those graphs G for which the sequence { HLk(G)} converges.