On a conjecture on the diameter of line graphs of graphs of diameter two


Harishchandra S. Ramane, Asha B. Ganagi, Ivan Gutman




Let $F_1$ be the $5$-vertex path, $F_2$ the graph obtained by identifying a vertex of a triangle with one end vertex of the $3$-vertex path and $F_3$ the graph obtained by identifying a vertex of a triangle with a vertex of another triangle. Let $diam(G)$ be the diameter of the graph $G$. In the paper [H. S. Ramane and I. Gutman, {ı Counterexamples for properties of line graphs of graphs of diameter two\/}, Kragujevac J. Math. {\bf 34} (2010), 147-150] it is conjectured that if $diam(G) \leq 2$ and if none of the $F_i$, $i = 1, 2, 3$, is an induced subgraph of $G$, then $diam(L^k(G)) > 2$ for some $k \geq 2$. In this paper we prove this conjecture.