[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i22p3600-d1522966.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Wei-Han Tsai & Jen-Ling Shang & Chiang Lin, 2024. "Graphs with a Fixed Maximum Degree and Order Attaining the Upper Bound on Minimum Status," Mathematics, MDPI, vol. 12(22), pages 1-9, November.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:22:p:3600-:d:1522966
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/22/3600/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/22/3600/
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:22:p:3600-:d:1522966. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.