(k + 1)-line graphs of k-trees

Let G be a k-tree of order larger than k +1 and let ℓ_k+1 (G) be its (k +1)-line graph. We introduce a new concept called the k-clique graph of G, and denote it by G/[k]. We show that G/[k] is a connected block graph and ℓ_k+1 (G) is isomorphic to the block graph of G/[k]. This provides an alternative proof for a recent result by Oliveira et al. that ℓ_k+1 (G) is a connected block graph. A relation between the Wiener index of G/[k] and the Wiener index of its block graph ℓ_k+1 (G) is obtained as a natural generalization of the relation between the Wiener index of a tree T and the Wiener index of its line graph L(T). We further show that there is a 1–1 correspondence between the set of the blocks of ℓ_k+1 (G) and the set of minimal separators of G. Another new concept called the separator-k-clique graph of G, denoted by G/[k]_S, arises naturally with the property that G/[k]_S is isomorphic to the block graph of ℓ_k+1 (G). By the Szeged-Wiener Theorem, the Wiener index and the Szeged index are equal for each of the connected block graphs G/[k], ℓ_k+1 (G) and G/[k]_S.