Minimum Degree Growth of the Iterated Line Graph

Abstract

Let ${\delta }_k$ denote the minimum degree of the $k^{th}$-iterated line graph $L^k(G)$. For any connected graph $G$ that is not a path, the inequality ${\delta }_k\ge 2{\delta }_k–2$ holds. Niepel, Knor, and Soltés [5] have conjectured that there exists an integer $K$ such that, for all $k\ge K$, equality holds; that is, the minimum degree ${\delta }_k$ attains the least possible growth. We prove this conjecture by extending the methods we used in [2] for a similar conjecture about the maximum degree.