Graphs with a Fixed Maximum Degree and Order Attaining the Upper Bound on Minimum Status

Wei-Han Tsai, Jen-Ling Shang () and Chiang Lin
Additional contact information
Wei-Han Tsai: Department of Mathematics, National Central University, Zhongli District, Taoyuan City 320317, Taiwan
Jen-Ling Shang: Department of Applied Chinese, Kainan University, Luzhu District, Taoyuan City 338103, Taiwan
Chiang Lin: Department of Mathematics, National Central University, Zhongli District, Taoyuan City 320317, Taiwan

Mathematics, 2024, vol. 12, issue 22, 1-9

Abstract: The status (or transmission) of a vertex in a connected graph is the sum of distances between the vertex and all other vertices. The minimum status (or minimum transmission) of a connected graph is the minimum of the statuses of all vertices in the graph. Previously, sharp lower and upper bounds have been obtained on the minimum status of connected graphs with a fixed maximum degree k and order n . Moreover, for 2 ≤ k ≤ n 2 , the following theorem about graphs attaining the maximum on the minimum status has also been proposed without proof. The theorem is as follows: Let G be a connected graph of order n with ▵ ( G ) = k , where 2 ≤ k ≤ n 2 . Then, the minimum status of G attains the maximum if and only if one of the following holds. (1) G is a path or a cycle, where k = 2 ; (2) G k , n is a spanning subgraph of G and G is a spanning subgraph of H k , n , where 3 ≤ k < n 2 ; and (3) either G n 2 , n is a spanning subgraph of G and G is a spanning subgraph of H n 2 , n or G n 2 , n is a spanning subgraph of G and G is a spanning subgraph of H n , where k = n 2 for even n ≥ 6 . For the integers n , k with 2 ≤ k ≤ n − 1 , the graph G k , n has the vertex set V ( G k , n ) = { x 1 , x 2 , ⋯ , x n } and the edge set E ( G k , n ) = { x i x i + 1 : i = 1 , 2 , ⋯ , n − k } ∪ { x n − k + 1 x j : j = n − k + 2 , n − k + 3 , ⋯ , n } ; the graph H k , n is obtained from G k , n by adding all the edges x i x j , where n − k + 2 ≤ i < j ≤ n ; and for even n ≥ 6 the graph H n is obtained from G n 2 , n by adding the edge x n 2 − 1 x n 2 + 2 and all the edges x i x j , where n 2 + 3 ≤ i < j ≤ n . This study provides the proof to complete the above theorem.

Keywords: status; transmission; minimum status; proximity (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/22/3600/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/22/3600/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:22:p:3600-:d:1522966

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().