On tree-connection of generalized line graphs

Abstract

The line graph $L(G)$ of a nonempty graph $G$ has the set of edges in $G$ as its vertex set where two vertices of $L(G)$ are adjacent if the corresponding edges of $G$ are adjacent. Let $k>2$ be an integer and let $G$ be a graph containing k-paths (paths of order $k$). The k-path graph $P_k(G)$ of $G$ has the set of k-paths of $G$ as its vertex set where two distinct vertices of $P_k(G)$ are adjacent if the corresponding k-paths of $G$ have a $(k-1)$-path in common. Thus, $P_2(G)=L(G)$ and $P_3(G)=L(L(G))$. Hence, the k-path graph $P_k(G)$ of a graph $G$ is a generalization of the line graph $L(G)$. Let $G$ be a connected graph of order $n>3$ and let $k$ be an integer with $2<k2$, then $P_3(T)$ is $k$-tree-connected. This conjecture was verified for $k=2,3$. In this work, we show that if $T$ is a tree of order at least 6 containing no vertices of degree 2, 3, 4, or 5, then $P_3(T)$ is 4-tree-connected and so verify the conjecture for the case when $k=4$.