## 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 language | English (US) |
---|---|

Pages (from-to) | 12-23 |

Number of pages | 12 |

Journal | Australasian Journal of Combinatorics |

Volume | 87 |

Issue number | 1 |

State | Published - Oct 2023 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics