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

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 WKd,t and WK-recursive pyramids WKPd,n. In this paper, we revise their results and determine the exact values of the rainbow connection numbers of WKd,2 for d=3 and 4. The rainbow connection numbers of WKd,2 are bounded between 4 and ⌊d2⌋+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 WKPd,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.

Keywords

• edge coloring
• rainbow path
• rainbow coloring
• rainbow connection number
• WK-recursive networks
• WK-recursive pyramids