Understanding depth-limited BFS time complexity
There are two cases.

First. $V-1 \leq E$. Then $O(V \cdot (V + E))$ and $O(V \cdot E)$ are equivalent.

Second. $E &lt; V-1$. Then graph is disconnected and the biggest component has size at most $E + 1$. The whole algorithm will consist of $V$ BFS runs each on the component which has at most $E + 1$ vertices and at most $E$ edges. So each BFS run will take $O(E)$ time and the whole algorithm - $O(VE)$.

Note: this reasoning does not depend on $k$.