The extremal graphs of order trees and their topological indices

Abstract

Recently, D. Vuki$\check{c}$evi$\acute{c}$ and J. Sedlar in \cite{Vuki} introduced an order "$⪯$" on ${\mathcal{T}}_n$, the set of trees on $n$ vertices, such that the topological index $F$ of a graph is a function defined on the order set $⟨{\mathcal{T}}_n,⪯⟩$. It provides a new approach to determine the extremal graphs with respect to topological index $F$. By using the method they determined the common maximum and/or minimum graphs of ${\mathcal{T}}_n$ with respect to topological indices of Wiener type and anti-Wiener type. Motivated by their researches we further study the order set $⟨{\mathcal{T}}_n,⪯⟩$ and give a criterion to determine its order, which enable us to get the common extremal graphs in four prescribed subclasses of $⟨{\mathcal{T}}_n,⪯⟩$. All these extremal graphs are confirmed to be the common maximum and/or minimum graphs with respect to the topological indices of Wiener type and anti-Wiener type. Additionally, we calculate the exact values of Wiener index for the extremal graphs in the order sets $⟨\mathcal{C}(n,k),⪯⟩$, $⟨{\mathcal{T}}_n(q),⪯⟩$ and $⟨{\mathcal{T}}_n^{\Delta },⪯⟩$.

27 pages