Which numbers are status differences?

作者：Lin, Hongying; Zhou, Bo^*

来源：APPLIED MATHEMATICS AND COMPUTATION, 2021, 399: 126004.

DOI：10.1016/j.amc.2021.126004

• Status difference
• Minimum status
• Maximum status
• Number of leaves
• Diameter
• Series-reduced tree

Given a connected graph G, the status S-G(x) of a vertex x of G is the sum of the distances from x to all other vertices in G, and the status difference of G is sd(G) = max(x,y is an element of)(V(G)) (S-G(x) - S-G(y)). The status difference is a useful descriptor in communication networks. We determine the numbers that can be the status differences of trees and connected graphs, respectively, with fixed order, and characterize the trees with the first a few smallest status differences when the order is fixed. Also, we identify the trees with maximum status difference over all trees with fixed maximum degree, number of leaves, and diameter, respectively, as well as the series-reduced trees with maximum status difference.