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

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)12-23
Number of pages12
JournalAustralasian Journal of Combinatorics
Volume87
Issue number1
StatePublished - Oct 2023

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Cite this