Minimum Status, Matching and Domination of Graphs. (2nd June 2020)

• Record Type: Journal Article
• Authors: Liang, Caixia; Zhou, Bo; Guo, Haiyan
• Is Part Of: Computer journal. Volume 64:Number 9(2021)
• Page Start: 1384
• Page End: 1392
• Publication Date: 2020-06-02
• Subjects: minimum status -- proximity -- matching number -- domination number -- minimum branch weight; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa057
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Given a graph, the status of a vertex is the sum of the distances between the vertex and all other vertices. The minimum status of a graph is the minimum of statuses of all vertices of this graph. We give a sharp upper bound for the minimum status of a connected graph with fixed order and matching number (domination number, respectively) and characterize the unique trees achieving the bound. We also determine the unique tree such that its minimum status is as small as possible when order and matching number (domination number, respectively) are fixed.