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 \geq 2\delta_k – 2\) holds. Niepel, Knor, and Soltés [5] have conjectured that there exists an integer \(K\) such that, for all \(k \geq 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.