Graph theory provides a powerful framework for modeling and analyzing communication networks, where reliability, security, and eficiency are crucial. Various coloring concepts have been proposed to ensure that networks can support secure and interference-free communication. One such concept is the strong k-rainbow index of a graph, introduced by Awanis and Salman [1], which measures the minimum number of colors needed to color the edges of a connected graph so that every set of k vertices is connected by a rainbow Steiner tree—a tree of minimum size whose edges have distinct colors. This parameter is closely tied to combinatorial optimization and connectivity theory, particularly through its relation to Steiner trees.

In the case of the strong 3-rainbow index, the aim is to guarantee minimum rainbow connectivity for every three vertices of a graph. When interpreted in a network model, vertices represent devices such as servers or routes, while edges represent direct communication links between these devices. Assigning distinct colors to the edges of a Steiner tree can be viewed as assigning diferent frequency channels or encryption keys to ensure interference-free and secure multi-terminal communication. Beyond its practical relevance, determining a strong 3-rainbow index also yields theoretical insights into how cycle constraints and structural properties of a graph influence its rainbow connectivity requirements. By minimizing the number of colors used while maintaining strong connectivity properties, the strong 3-rainbow index contributes to the eficient use of network resources.

Before we discuss the formal definitions of a strong k-rainbow index, the readers are advised to understand the formal definitions of a k-rainbow index first. Let G be a connected graph of order that admits an edge-coloring. The size of is denoted by . A tree in is a rainbow tree if all edges of the tree are colored with distinct colors. Let k be an integer with . In this paper, we always consider as a k-subset of . The k-rainbow index of is the smallest number of colors required in an edge-coloring of so that every set in is connected by a rainbow tree. The 2-rainbow index of G is also known as the rainbowconnection number [2] . Hence, it is easy to see that

Chakraborty et al. in [3] proved a conjecture given by Caro et al.[4] which states that computing the rc of a graph is an NP-Hard problem. Hence, it is more dificult to compute the of a graph. Some previous researchers studied the upper bounds for of graphs (e.g. [5, 6, 7]), the of some graphs and some graph operations (e.g., [8], [6], [9][9][10], [11]), and the characterization of graphs with certain values of (e . g . , [9], [12]). We refer to [13, 14] for some detailed surveys on 3-rainbow index.

Later, Awanis and Salman [1] proposed the concept of a strong k-rainbow index. A tree of minimum size in G that connects S is called a Steiner S-tree and the minimum size is defined as the Steiner distance of . The Steiner tree is also known as the geodesic[2]. The strong k-rainbow index of is the smallest number of colors required in an edge-coloring of so that every set S in is connected by a rainbow Steiner S-tree. Such an edge-coloring of is called a strong k-rainbow coloring of G. The strong 2-rainbow index of is also known as the strong rainbow connection number of [2]. Awanis and Salman [1] provided sharp lower and upper bounds for the srx3 of a connected graph that is

where sdiam denotes the k-Steiner diameter of and is defined as max is a k-subset of

In the same paper, Awanis and Salman [1] established the edge-coloring rules for connected graphs containing at least two bridges. Let and be these two bridges. Since consists of three components, say , and , without loss of generality, we may assume that , and . Under this condition, any rainbow Steiner tree connecting a set S of three vertices that includes vertices and must necessarily contain both bridges and . This directly leads to Observation 1.1. According to this observation and Eq. (1), Awanis and Salman further established that of trees is equal to its size, as stated in Theorem 1.2.

Observation 1.1.[1]Let G be a strong 3-rainbow colored connected graph of order and f are any two bridges of G, then e and f are colored with distinct colors.

Theorem 1.2.[1]For a tree of order , srx3(Tn) = ∥Tn∥ = n − 1.

Many researchers have investigated the of graphs resulting from some graph operations, such as some certain graphs and their amalgamation [1], the edge-amalgamation of some graphs [15], the comb product of a tree and a connected graph [16], and the edge-comb product of a path and a connected graph [17]. In addition, we are also interested in exploring the characteristics of graphs with , as presented in [18].

Since a tree is an acyclic connected graph, adding even a single edge necessarily creates a graph that contains at least one cycle. Cycles, especially those with small girths, are of particular interest because they generate alternative Steiner trees between three vertices, which may afect the existence and structure of rainbow Steiner trees. Therefore, adding one or two edges to a tree increases the graph’s connectivity and redundancy. These structural changes may impact the minimum number of colors required to ensure strong 3-rainbow connectivity.

A natural question then arises: What happens to the when at least one edge is added to a tree? Specifically, does the of the resulting graph remain equal to its size? Motivated by this, the present study investigates the of graphs containing some cycles, with a particular focus on unicyclic and bicyclic graphs. First, we establish an upper bound for the of these graphs and demonstrate that the bound is sharp. These results are presented in Section 2. Subsequently, we determine the exact values of the for unicyclic and bicyclic graphs, which are presented in Sections 3 and 4, respectively.

Several notations are defined in this paper as follows. For an integer x with , let denotes a set of all integers x. For an integer t with let

Note that if , then there exists exactly one path connecting the two cycles in . We denote as such a path. Since denotes a set of all bridges in for , it follows from Observation 1.1 that

Now, we are ready to provide an upper bound of the for . This result is given in the following theorem.

Theorem 2.1.Forand letbe a connected graph of order n containing exactly t cycles of length at least 3. Then

Proof. For , it follows from Eq.(1) that srx

For , we show that srx3 by defining a strong rainbow coloring , which can be obtained by defining and assigning colors to the remaining edges of . Now, we show that every three vertices of is connected by a rainbow Steiner tree by considering the following properties.

Thus, the theorem holds.

The upper bound provided in Theorem 2.1 is sharp. Theorem 2.5 shows that , where is a connected graph containing exactly t odd cycles of length at least 7. Before we proceed to this theorem, we first need several preliminary results as given in Theorem 2.2 and Lemmas 2.3 and 2.4.

Theorem 2.2. [1]For a cycle of order

According to theorem above, it is not dificult to define a strong 3-rainbow coloring of for , since all edges of the cycle can simply be assigned with distinct colors. The challenge lies in defining such an edge-coloring for smaller values of where fewer colors must be used while still maintaining the existence of rainbow Steiner trees. Figure 1 below illustrates the strong 3-rainbow colorings of for . Since the graphs studied in this paper contain at most two cycles, and the rainbow Steiner tree connecting every three vertices within the cycle must lies in it, these edge-coloring illustrations are essential to guarantee the existence of rainbow Steiner trees that support the results established in Sections 3 and 4.

Lemma 2.3.For and , let G be a strong 3-rainbow colored connected graph of order n containing a cycle and is an arbitrary bridge of then e and f are colored with distinct colors.

Proof. Let . Suppose that there exist and a bridge so that e and are colored with the same color. Let for and , and assume that . Observe that every rainbow Steiner must contain edges e and , which is a contradiction since these two edges have the same color. □

To assist the reader’s understanding, an illustration of Lemma 2.3 is provided in Figure 2.

For further discussion, we always let if is odd or if is even, for .

Lemma 2.4.For , let be a bicyclic graph of order n containing two cycles and of length at least 3. is a strong 3-rainbow coloring of , then

Proof.

To assist the reader’s understanding, an illustration of Lemma 2.4 is provided in Figure 3.

Now, we are ready to prove the sharpness of the upper bound in Theorem 2.1, as given in the following theorem.

Theorem 2.5.For and , let be a connected graph of order n containing exactly t odd cycles of length at least 7. Then, .

Proof. For each , let be an odd cycle of length contained in It follows from Theorem 2.1 that srx. For the lower bound, suppose that srx3. Then there exists a strong 3-rainbow coloring . Let Y be the set of colors assigned to the edges of for all . According to Lemma 2.3, . Thus, it follows from Eq. (2) that . Now, we distinguish two cases.

for all i∈ [1, t]. According to Lemma 2.3, c(X)∩ Y =∅. Thus, it follows from Eq.(2) that |Y|≤Pti=1gi− t. Now, we distinguish two cases

Case 1.t = 1.

It means . If , then there are at least two edges of that are colored the same, contradicting Theorem 2.2. If is a unicyclic graph and not a cycle, then we have . This implies there are at least two edges of that are colored the same, contradicting Theorem 2.2.

Case 2. t = 2

It means c : . Note that . However, it follows from Theorem 2.2 and Lemma 2.4 that which is impossible. □

Following the result above, an immediate question arises: What is the for that does not satisfy the premise of Theorem 2.5? The answers to this question are given in Sections 3 and 4.

Let be a unicyclic graph of order and girth . Chartrand et al. [6] have determined the of unicyclic graphs as follows.

Theorem 3.1. [6]For , let be a unicyclic graph of order n and girth . Then,

Motivated by the result above, we are interested in studying the of unicyclic graphs. Awanis and Salman in [1] have determined the of cycles (see Theorem 2.2). Hence, in this section, we determine the of unicyclic graphs that is not a cycle as given in the following theorem.

Theorem 3.2.For and , let be a unicyclic graph of order n and girth that is not a cycle. Then,

Proof. Note that . It follows from Eq. (1) and Theorem 3.1 that s for and srx3 for . Meanwhile for or , it follows from Eq. (2), Theorem 2.2, and Lemma 2.3 that .

Next, we prove the upper bound. For each , let be the th bridge of As srx for , and for or by Theorem 2.2, there exists a strong 3-rainbow coloring of . Thus, we define a strong 3-rainbow coloring of as follows.

Now, we show that every three vertices of is connected by a rainbow Steiner tree by considering the following properties.

As an example, let be an unicylic graph of order and girth According to Theorem 2.2 , we have . Let be a strong 3-rainbow coloring of that follows the edge-coloring pattern illustrated in Figure 1. Based on the edge-coloring c defined in the proof of theorem above, we assign the first 4 colors to the edges of using the edge-coloring , and then assign colors to the bridges of . As a result, we obtain a strong 3-rainbow coloring of as illustrated in Figure 4(a). By using a similar procedure, we also obtain a strong 3-rainbow coloring of with order and girth as illustrated in Figure 4(b).

We now conclude this section by outlining the main results obtained as given in the following corollary.

Corollary 3.3.For , let be a unicyclic graph of order n and girth . Then,

Recall that adding an edge to a tree creates a unicyclic graph. Following the corollary above, we obtain that the of unicyclic graphs is equal to its size if it has a girth of 7 or at least 9. Otherwise, its srx is less than its size.

For and , let be a bicyclic graph of order n containing two cycles and . Recall that we denote for each andas the only path connecting and . Let be an arbitrary bridge of . Thus, it is clear that for each , there exists exactly one vertex for such that for all q ∈ [1, gi]with .

In this section, we provide the exact value of the of bicyclic graphs. We first need the following results.

Observation 4.1. For , let be a strong 3-rainbow colored bicyclic graph of order n containing two cycles. Let one of its cycles be . Let for distinct and be an arbitrary bridge of such that . Then, edges and should have distinct colors from e.

Proof. Let . Assume that . Thus, by considering and , it is clear that edges and should have distinct colors from bridge e. □

The following observation is an immediate consequence of Observation 4.1.

Observation 4.2.For , let be a strong 3-rainbow colored bicyclic graph order n containing two cycles. Let one of its cycles be . Then, at most one color of the bridges can be used on .

Proof. Let . Let c be a strong 3-rainbow coloring of Suppose that there are two colors of the bridges of , say 1 and 2, which are used on . Let and be two distinct bridges of with and . Recall that there exist such that for and for w . Assume that and . Thus, it follows by Observation 4.1 that edges and may be colored with 1 and 2, respectively. If , then there exists an edge of with colors 1 and which is impossible. Thus, However, observe that every rainbow Steiner -tree must contain bridges e and and two edges of , say f and , where at least one of and is colored with 1 or 2, a contradiction. □

Let c be a strong 3-rainbow coloring of . For with it follows from Theorem 2.2 that we need at least distinct colors to color the edges of . Hence, we assign these colors to the edges of by adopting the edge-coloring pattern illustrated in Figure 1, as given in (A1). This ensures the existence of a rainbow Steiner tree connecting every three vertices of .

(A1) For , define and . For define and . For , define and . Furthermore, assign distinct colors that are not used to the preceding edges to the remaining edges of

As an example, let be one of the cycles contained in . By using the edge-coloring rules given in (A1) , we assign three distinct colors, say and so that , and . Hence, we have an edge-coloring of as illustrated in Figure 5. By using a similar argument, we also obtain edge-colorings of and as illustrated in Figure 5.

We now determine the of bicyclic graphs as given in the following theorem.

Theorem 4.3.For and , let be a bicyclic graph of order n containing two cycles of lengths and . Then

Proof. To prove the exact value of , it is necessary to establish both the lower and upper bounds. The lower bound is obtained by considering two main cases based on the lengths of the cycles in both cycles have length at least 4, and (ii) at least one cycle has length 3. In each case, the bound is derived by applying key lemmas and theorems linking cycle structure to rainbow connectivity. For the upper bound, we define a strong 3-rainbow coloring in a case-by-case manner, mirroring the cycle-length distinctions, with the following rules: (i) cycles are colored to guarantee internal rainbow Steiner trees, and (ii) bridges are assigned distinct colors not used in the cycles to prevent overlap in any Steiner tree spanning both cycle and tree parts. For every three vertices, the coloring guarantees a rainbow Steiner tree entirely within a cycle or through uniquely colored bridges. In each case, the number of colors used matches the lower bound, thereby establishing sharpness. Having set these proof sketches, we are now ready to present the detailed proofs.

Note that . First, we prove the lower bound. We distinguish two cases as follows.

Case 1. The two cycles contained in have length at least 4.

Let c be a strong 3-rainbow coloring of . Note that for distinct , we have

by Lemmas 2.3 and 2.4(ii) . Without loss of generality, let and . Thus, it follows from Eq. (2), Theorem 2.2, and Lemma 2.4(i) that srx for and or , for and , for and or , and for .

We now consider the case where both and are equal to or at least 9. If and are both odd, or if and have distinct parity, then by using a similar argument, we have . Thus, the remaining case to consider is when both and are even. According to Eq. (3), we need at least distinct colors to color all edges of and . Now, consider edges and . By using Theorem 2.2 and considering for , we have . This forces . However, observe that every rainbow Steiner -tree must contain edges , and either or , a contradiction.

Case 2. At least one of the cycles contained in has length 3.

Without loss of generality, let and . To simplify the discussion, let us denote . Suppose that srx3 . Then there exists a strong 3-rainbow coloring . Since by Eq. (2), we have at most remaining colors. Let the set of these remaining colors be denoted by ]. Further, we distinguish three subcases depending on the length as follows.

Subcase 2.1.

Since , we have . For . If does not contain bridges, then and . However, by considering , we need at least three distinct colors to color edge and two edges in a rainbow Steiner -tree, which is impossible. Thus, contains bridges. Note that for each . However, according to Observation 4.2, edges or should be colored with colors from Y for each Without loss of generality, let Since fpr , let and . Now, consider edge . Note that . If , then let be the bridge of where , and assume that . Now, consider edge According to Observation 4.2 , . This forces . However, there is no rainbow Steiner , a contradiction. If , then. This forces . Let be the bridge of where , and assume that . However, there is no rainbow Steiner a contradiction.

Meanwhile for . Since by Lemma 2.3, we have . Since by Lemma 2.4(i), without loss of generality, let and. Now, consider edges . Since by Lemma 2.4(ii) we have . According to Observation 4.2, edges should be colored with 3. Thus, without loss of generality, we have either and or . By using a similar argument as case , we will obtain a contradiction.

Subcase 2.2.

Since , we have . Note that and by Theorem 2.2 and Lemma 2.3, respectively. Thus, . Now, consider edges and . By Lemma 2.4(ii). This forces , contradicting Observation 4.2.

Subcase 2.3. or

Since , we have . By using a similar argument as Subcase 2.2, we obtain that , contradicting Observation 4.2.

The following figure presents an illustration of the contradiction arising in Subcases 2.2 and 2.3.

Now, we proceed to prove the upper bound. For are equal to 7 or at least 9, it follows from Theorem 2.1 that

For and , we define a strong 3-rainbow coloring c of as follows.

(1) Define and

(2) For , do step (a). For , do step (b). For , do step (c). For g = 7 or g ≥ 9, do step (d)

(a) Define and . Furthermore, \end{document} ]]>

bridges of

(b) Define and . Furthermore, i 7 \end{document} ]]> , then assign colors to the bridges of .

(c) Assign colors to the edges of by using the edgecoloring rules given in (A1) such that . Furthermore, if g _ { 2 } + 3 \end{document} ]]> , then assign colors to the bridges of .

(d) Assign colors to the remaining edges of such that .

For and , we define a strong 3-rainbow coloring c of as follows.

(1) Define and .

(2) For , do step (a). For , do step (b). For or , do step (c).

(a) Define and . Furthermore, 8 . \end{document} ]]> , then assign colors to the bridges of

(b) Assign colors to the edges of by using the edge-coloring rules given in (A1) . Furthermore, if g _ { 2 } + 4 \end{document} ]]> , then assign colors to the bridges of

(c) Assign colors to the remaining edges of .

For , and , we define a strong 3-rainbow coloring c of as follows.

(1) Assign colors 1, to the edges of by using the edge-coloring rules given in (A1) such that

(2) For , do step (a). For or , do step (b).

(a) Assign colors to the edges of by using the coloring rules given in (A1) such that Furthermore, if g _ { 1 } + g _ { 2 } \end{document} ]]> , then assign colors to the bridges of

(b) Assign colors to the remaining edges of such that

The next step is to show that there exists a rainbow Steiner tree connecting every 3-subset of . Since the edge-colorings c assign distinct colors to all bridges of and ensure that for all , it sufices to consider the subsets under the following two cases.

(i) for some . For , the existence of a rainbow Steiner S-tree is immediate. Moreover, for , the edgecolorings c assign distinct colors to the edges of according to the edge-coloring rules given in (A1), while for or , all edges of are colored with distinct colors. Thus, in all these cases, the existence of a rainbow Steiner S-tree is also guaranteed.

(ii) and . Observe that there exists a rainbow u geodesic in rainbow Steiner -tree T in , and a rainbow geodesic such that for distinct . Thus, the tree is a rainbow Steiner S-tree.

As an example, let be a bicyclic graph of order with and . According to the edge-coloring c defined in the proof of theorem above, we first assign colors 1 and 2 to the edges of so that the edges and receive the color 1, and then assign colors 2, 3 and 4 to the edges of so that the edge receives color 2. The remaining edges, which are the bridges of , are then colored with colors . As a result, we obtain a strong 3-rainbow coloring of as illustrated in Figure 7(a) . By using a similar procedure, we also obtain a strong 3-rainbow coloring of with n = 24, and , as illustrated in Figure 7(b).

According to Theorem 4.3, it can be concluded that the of bicyclic graphs, which is a graph obtained by adding two edges to a tree, is always less than its size.

It is known that (see Theorem 1.2). Therefore, this paper investigated how the addition of one or two edges to a tree afected the srx of the resulting graphs. We first provided sharp upper bounds for where G is a unicyclic or bicyclic graph, and then determined the exact values of for such graphs. Our results showed that if is a unicyclic graph with girth 7 or at least 9; in all other cases, . More specifically, Corollary 3.3 and Theorem 4.3 showed that for if G is a connected graph containing t odd cycles of lengths at least 7. These results raise a natural question regarding the sharpness of this bound for connected graphs with more cycles, as formulated belows.

Problem 5.1.For , is the upper bound always sharp for a connected graph G containing t odd cycles of lengths at least 7?

Additionally, it is important to note that adding two edges to a tree may produce a graph containing exactly three cycles, one of which is commonly known as a theta graph. This observation naturally motivates further investigation of the following problem.

Problem 5.2.What is the exact values of where G is a theta graph of order

Moreover, exploring the behavior of in general cyclic graphs presents a promising direction for future research. We hope that the results presented in this paper provide a foundation for the broader characterization of the for cyclic graphs.