Maximum Degree Growth of the Iterated Line Graph

Abstract

Let $\Delta_k$ denote the maximum degree of the $k^{\rm th}$ iterated line graph $L^k(G)$. For any connected graph $G$ that is not a path, the inequality $\Delta_{k+1}\leq 2\Delta_k-2$ holds. Niepel, Knor, and Šoltés have conjectured that there exists an integer $K$ such that, for all $k\geq K$, equality holds; that is, the maximum degree $\Delta_k$ attains the greatest possible growth. We prove this conjecture using induced subgraphs of maximum degree vertices and locally maximum vertices.