Optimal connectivity of second order iterated line graphs

Abstract

The line graph $L(G)$ of a graph $G$ is defined to be the simple graph whose vertices are the edges of $G$, where two vertices in $L(G)$ are adjacent if and only if the corresponding edges in $G$ are incident with a common vertex, and define $L^2(G)=L(L(G))$. For positive integers $d$ and $k$, the function $κ_{L^2}(d,k) = \inf\{κ(L^2(G)): κ'(G) \ge k \mbox{ and } δ(G) \ge d\}$ has been investigated. Niepel and Knor proved that ${\kappa }_{L^2}(d,1)\ge d-1$, for any integer $d\ge 3$. In this research, it is proved that if $d\ge 3$ and $k\ge 1$, then ${\kappa }_{L^2}(d,k)=\min \{f(d,k),4d-6\}$, where \begin{equation} f(d,k) = \left\{ \begin{array}{ll} k(d-k), & \mbox{ if $1\le k\le \lfloor \frac{d}{2}\rfloor$, } \\ kd-k^2+2k(\lceil \frac{d}{2}\rceil)-(\lceil\frac{d}{2}\rceil)d, & \mbox{ if $\lfloor \frac{d}{2}\rfloor <k<\frac{3d-1}{4}$, } \\ kd-k^2+2k\lfloor \frac{d}{2}\rfloor-2(\lfloor \frac{d}{2}\rfloor)^2, & \mbox{ if $\frac{3d-1}{4}\le k<d$, }\\ d(\lceil \frac{d}{2}\rceil), & \mbox{ if } d=k. \end{array} \right.\nonumber \end{equation}

v2: Revised proofs and corrected minor typos