Extremal Trees with Respect to Bi-Wiener Index

期刊论文
发表日期：

2024年8月12日

查看全文

Ximei Chen,
Sasan Karimi,
Kexiang Xu,
Marty Lewinter,
Eric Choi,
Anthony Delgado,
Tomislav Došlić

摘要

In this paper we introduce and study a new graph-theoretic invariant called the bi-Wiener index. The bi-Wiener index $W_b(G)$ $W_{b} (G)$ of a bipartite graph G is defined as the sum of all (shortest-path) distances between two vertices from different parts of the bipartition of the vertex set of G. We start with providing a motivation connected with the potential uses of the new invariant in the QSAR/QSPR studies. Then we study its behavior for trees. We prove that, among all trees of order $n\ge 4$ $n \geq 4$ , the minimum value of $W_b$ $W_{b}$ is attained for the star $S_n$ $S_{n}$ , and the maximum $W_b$ $W_{b}$ is attained at path $P_n$ $P_{n}$ for even n, or at path $P_n$ $P_{n}$ and $B_n(2)$ $B_{n} (2)$ for odd n where $B_n(2)$ $B_{n} (2)$ is a broom with maximum degree 3. We also determine the extremal values of the ratio $W_b(T_n)/W(T_n)$ $W_{b} (T_{n}) / W (T_{n})$ over all trees of order n. At the end, we indicate some open problems and discuss some possible directions of further research.