Towards a characterization of convergent sequences of $P_n$-line graphs

Alvaro Carbonero

Published 2021-07-07Version 1

Let $H$ and $G$ be graphs such that $H$ has at least 3 vertices and is connected. The $H$-line graph of $G$, denoted by $HL(G)$, is that graph whose vertices are the edges of $G$ and where two vertices of $HL(G)$ are adjacent if they are adjacent in $G$ and lie in a common copy of $H$. For each nonnegative integer $k$, let $HL^{k}(G)$ denote the $k$-th iteration of the $H$-line graph of $G$. We say that the sequence $\{ HL^k(G) \}$ converges if there exists a positive integer $N$ such that $HL^k(G) \cong HL^{k+1}(G)$, and for $n \geq 3$ we set $\Lambda_n$ as the set of all graphs $G$ whose sequence $\{HL^k(G) \}$ converges when $H\cong P_n$. The sets $\Lambda_3, \Lambda_4$ and $\Lambda_5$ have been characterized. To progress towards the characterization of $\Lambda_n$ in general, this paper defines and studies the following property: a graph $G$ is minimally $n$-convergent if $G\in \Lambda_n$ but no proper subgraph of $G$ is in $\Lambda_n$. In addition, prove conditions that imply divergence, and use these results to develop some of the properties of minimally $n$-convergent graphs.