Title: Some computational aspects of terminal Wiener index

Authors: K. Viswanathan Iyer; A. Sulphikar

Addresses: Department of Computer Science and Engineering, National Institute of Technology, Trichy, 620015, Tamilnadu, India ' Department of Computer Science and Engineering, National Institute of Technology, Trichy, 620015, Tamilnadu, India

Abstract: The terminal Wiener index of a tree T is defined as the sum of the distance between all pairs of pendent vertices in T. The concept of terminal Wiener index is used in mathematics as well as in chemistry. Several papers address the question: "What positive integers can be terminal Wiener indices of trees of a certain type?". The question has already been answered for certain types of trees. In this paper, we consider full binary trees and binomial trees. Since both of these trees can be defined recursively, we introduce a common method to derive expressions for the terminal Wiener index. Algorithms are already available to compute Wiener index of a tree in linear time. We show that if the Wiener index of a tree can be computed in linear time then its terminal Wiener index can also be computed in linear time. We also describe a linear time algorithm to compute terminal Wiener index of a tree.

Keywords: terminal Wiener index; full binary tree; binomial tree; Wiener index; distance in graphs.

DOI: 10.1504/IJCSM.2024.137262

International Journal of Computing Science and Mathematics, 2024 Vol.19 No.2, pp.123 - 132

Received: 18 Nov 2021
Accepted: 14 Mar 2023
Published online: 08 Mar 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article