IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i7p944-d1362250.html
   My bibliography  Save this article

Rainbow Connection Numbers of WK-Recursive Networks and WK-Recursive Pyramids

Author

Listed:
  • Fu-Hsing Wang

    (Department of Information Management, Chinese Culture University, Taipei 11114, Taiwan)

  • Cheng-Ju Hsu

    (Department of Information Management, Chien Hsin University of Science and Technology, Taoyuan City 32097, Taiwan)

Abstract

An edge coloring of a graph G results in G being rainbow connected when every pair of vertices is linked by a rainbow path. Such a path is defined as one where each edge possesses a distinct color. A rainbow coloring refers to an edge coloring that guarantees the rainbow connectedness of G . The rainbow connection number of G represents the smallest quantity of colors required to achieve rainbow connectedness under a rainbow coloring scheme. Wang and Hsu (ICICM 2019: 75–79) provided upper bounds on the size of the rainbow connection numbers in WK-recursive networks WK d , t and WK-recursive pyramids WKP d , n . In this paper, we revise their results and determine the exact values of the rainbow connection numbers of WK d , 2 for d = 3 and 4. The rainbow connection numbers of WK d , 2 are bounded between 4 and ⌊ d 2 ⌋ + 2 for d > 4 . In addition to our previous findings, we further investigate and determine upper bounds for the size of the rainbow connection numbers of WKP d , n . This involves analyzing various aspects of the graph structure and exploring potential limitations on the rainbow connection numbers. By establishing these upper bounds, we gain deeper insights into the potential range and constraints of the rainbow connection numbers within the given context.

Suggested Citation

  • Fu-Hsing Wang & Cheng-Ju Hsu, 2024. "Rainbow Connection Numbers of WK-Recursive Networks and WK-Recursive Pyramids," Mathematics, MDPI, vol. 12(7), pages 1-11, March.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:7:p:944-:d:1362250
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Sourav Chakraborty & Eldar Fischer & Arie Matsliah & Raphael Yuster, 2011. "Hardness and algorithms for rainbow connection," Journal of Combinatorial Optimization, Springer, vol. 21(3), pages 330-347, April.
    2. Yingbin Ma & Zaiping Lu, 2017. "Rainbow connection numbers of Cayley graphs," Journal of Combinatorial Optimization, Springer, vol. 34(1), pages 182-193, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Qingqiong Cai & Xueliang Li & Yan Zhao, 2016. "The 3-rainbow index and connected dominating sets," Journal of Combinatorial Optimization, Springer, vol. 31(3), pages 1142-1159, April.
    2. Nie, Kairui & Ma, Yingbin & Sidorowicz, Elżbieta, 2023. "(Strong) Proper vertex connection of some digraphs," Applied Mathematics and Computation, Elsevier, vol. 458(C).
    3. Ma, Yingbin & Zhang, Xiaoxue, 2023. "Graphs with (strong) proper connection numbers m−3 and m−4," Applied Mathematics and Computation, Elsevier, vol. 445(C).
    4. Ma, Yingbin & Zhu, Wenhan, 2022. "Some results on the 3‐total‐rainbow index," Applied Mathematics and Computation, Elsevier, vol. 427(C).
    5. Yingbin Ma & Zaiping Lu, 2017. "Rainbow connection numbers of Cayley graphs," Journal of Combinatorial Optimization, Springer, vol. 34(1), pages 182-193, July.

    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:7:p:944-:d:1362250. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.