Logo

Download

Title:
On the Wiener Index of Graphs with Given Dissociation Number
Authors:
Volume
96
Issue
3
Year
2026
Pages
975-996
Abstract

For a graph \( G=(V_G,E_G) \), a subset \( S\subseteq V_G \) is called a dissociation set if the induced subgraph \( G[S] \) does not contain \( P_3 \) as a subgraph. A maximum dissociation set of \( G \) is a dissociation set with the maximum cardinality and its cardinality is called the dissociation number of \( G \). In this paper, among all trees, bipartite graphs and general connected graphs with fixed order and dissociation number, the sharp lower bounds of the Wiener index are determined and the corresponding extremal graphs are characterized, respectively. Furthermore, the graphs having the maximum Wiener indices with fixed order \( n \) and dissociation number \( \varphi\in\{2,\left\lceil\frac{2}{3}n\right\rceil,n-2, n-1\} \) are also characterized, respectively.