Rainbow connection numbers of some classes of $s$-overlapping $r$-uniform hypertrees with size $t$

1.   Introduction

Connectivity is one of the fundamental subjects in graph theory that is interesting to discuss combinatorically and algorithmically. One of the concepts that researchers have developed in connectivity is the concept of rainbow connection. Chartrand et al. developed the rainbow connection concept in 2008, after the 9/11 attacks in 2001. The incident was thought to have occurred due to weaknesses in the security of information transfer between secret agents ^[1]. Therefore, the rainbow connection concept was developed to determine the minimum number of passwords required to exchange encrypted information between two agents. The concept has been implemented in general graph classes, including tree, complete, cycle, wheel, and complete multipartite graphs ^[2]. Researchers have intensively studied and implemented it in other classes of graphs. Rainbow connections on graph operations, including comb product ^[3,4], corona ^[5,6], amalgamation ^[7], direct product ^[8], strong product ^[8], lexicographic product ^[8], and cartesian product ^[9], have been studied. The rainbow connection numbers of special graphs, for examples, flowers ^[10], origamis ^[11], pizzas ^[11], $n$-crossed-prisms ^[12], stellars ^[13], pencils ^[14], subdivided-roofs ^[15], and rockets ^[16], have also been shown. Similarly, for dense graphs ^[17], sparse graphs ^[18], and random graphs ^{[19,20,21,22]}. In this case, there may be one or more secure paths of information exchange between two agents, such that the password used in each selected path will be different. If the information exchange involves more than two agents from different divisions, the concept of a rainbow connection of a graph can be extended to a hypergraph. In the context of a hypergraph, each agent in a division must have the same password information so that when they receive the encrypted data, they can open it. As such, Carpentier et al. developed the concept of rainbow connections in hypergraphs in 2014 ^[23].

The general terms and definitions in this article refer to Voloshin ^[24]. A hypergraph is a pair $\mathcal{H} = (X(\mathcal{H}), \mathcal{E}(\mathcal{H}))$, where $X(\mathcal{H}) = \{x_1, x_2, \ldots, x_n\}$ is a non-empty finite set and $\mathcal{E}(\mathcal{H}) = \{E_1, E_2, \ldots, E_t\}$ is a collection of subsets of $X(\mathcal{H})$ where $E_i\neq \emptyset$ for each $i\in\{1, 2, \ldots, t\}$. We call $X(\mathcal{H})$ and $\mathcal{E}(\mathcal{H})$ the vertex set and the edge set of $\mathcal{H}$, respectively. A hypergraph is said to be non-trivial if $\mathcal{E}(\mathcal{H}) \neq \emptyset$ ^[25]. The order and the size of $\mathcal{H}$ refer to the number of vertices and edges of $\mathcal{H}$, denoted by $|X(\mathcal{H})|$ and $|\mathcal{E}(\mathcal{H})|$, respectively. If every edge contains precisely $r$ vertices, $\mathcal{H}$ is called an $r$-uniform hypergraph. An alternating sequence $x_1E_1x_2E_2x_3\ldots x_{\ell}E_{\ell}x_{\ell+1}$ with distinct vertices $x_1, x_2, x_3, \ldots, x_{\ell}, x_{\ell+1}$ and distinct edges $E_1, E_2, \ldots, E_\ell$, where ${\{x_i, x_{i+1}\}\subseteq E_i}$ for every $i\in \{1, 2, \ldots, \ell\}$ is called an $x_1$-$x_{\ell+1}$ path ^[26]. For simplification, we write an alternating sequence $x_1E_1x_2E_2x_3\ldots x_{\ell}E_{\ell}x_{\ell+1}$ to $x_1E_1-E_2-\ldots -E_{\ell}x_{\ell+1}$. A hypergraph $\mathcal{H}$ is said to be connected, if for any pair of its vertices, there is a path connecting them.

Let $\mathcal{H} = (X(\mathcal{H}), \mathcal{E}(\mathcal{H}))$ be a hypergraph and $G = (X(G), S(G))$ be a connected graph over the vertex set $X(G) = X(\mathcal{H})$ and with edge set $S(G)$. Then, $G$ is called a host graph of $\mathcal{H}$ if every $E\in \mathcal{E}(\mathcal{H})$ induces a connected subgraph in $G$ ^[24]. It means that the hypergraph $\mathcal{H}$ is spanned by the graph $G$ ^[27]. If the host graph is a class of graphs: tree, path, star, broom, double-star, caterpillar, and centipede, they are called hypertree, hyperpath, hyperstar, broom hypergraph, double-star hypergraph, caterpillar hypergraph, and centipede hypergraph, respectively. Paths, stars, brooms, double-stars, caterpillars, and centipedes are tree graphs. Here, we refer to the definition of broom graphs in ^[28], double-star graphs in ^[29], caterpillar graphs in ^[30], and centipede graphs in ^[31].

This article considers non-trivial, connected, and simple hypergraphs. The concept of a rainbow connection in hypergraphs was introduced by Carpentier et al. ^[23] as follows: Let the hypergraph $\mathcal{H} = (X(\mathcal{H}), \mathcal{E}(\mathcal{H}))$ be a non-trivial connected hypergraph. For $\mu \in \mathbb{N}$, an edge $\mu$-coloring of $\mathcal{H}$ is a function $c : \mathcal{E}(\mathcal{H}) \rightarrow \{1, 2, \ldots, \mu\}$. A $u$-$v$ path in $\mathcal{H}$ is called a rainbow path if every edge of the path has a distinct color. An edge coloring of $\mathcal{H}$ is said to be rainbow connected if for any two vertices $u$ and $v$ in $X(\mathcal{H})$, there exists a rainbow path between them. A rainbow connected $\mu$-coloring of $\mathcal{H}$ is a rainbow connected coloring of $\mathcal{H}$ utilizing $\mu$ colors. An $rc(\mathcal{H})$ represents the smallest positive integer $\mu$ such that a rainbow connected $\mu$-coloring of $\mathcal{H}$ exists.

Carpentier et al. ^[23] obtained a lower bound for the rainbow connection number of a hypergraph. If the diameter of $\mathcal{H}$ is the maximum distance of each pair of vertices in $\mathcal{H}$, denoted by $diam(\mathcal{H})$, then the rainbow connection number of a hypergraph satisfies

Inspired by Schiermeyer ^[32] about a lower bound of the rainbow connection number of a graph, in this article, we improve a lower bound of the rainbow connection number of a hypergraph stated by Carpentier et al.^[23]. In a hypergraph, a pendant edge is an edge that contains a pendant vertex (a vertex of degree 1). Let $\mathcal{H} = (X(\mathcal{H}), \mathcal{E}(\mathcal{H}))$ be a connected hypergraph with $|\mathcal{E}(\mathcal{H})|\geq 1$ and $t_p(\mathcal{H})$ be the number of pendant edges in $\mathcal{H}$. We show that $rc(\mathcal{H})\geq t_p(\mathcal{H})$. Suppose that $rc(\mathcal{H})\leq t_p(\mathcal{H})-1$, then at least two pendant edges are provided with the same color. This result is a contradiction since every pendant edge must have a distinct color. Now, we show $rc(\mathcal{H})\geq \max\{diam(\mathcal{H}), t_p(\mathcal{H})\}$. If $t_p(\mathcal{H})\leq diam(\mathcal{H})$, by the definition of rainbow connection, we get $rc(\mathcal{H})\geq diam(\mathcal{H})$. Conversely, if $t_p(\mathcal{H}) > diam(\mathcal{H})$, based on the previous explanation, $rc(\mathcal{H})\geq t_p(\mathcal{H})$. We get the following Lemma 1.1. We note that the lower bound in Lemma 1.1 is strict, and we will show the proof in Theorem 2.1 and Corollary 2.3.

Lemma 1.1. Let $\mathcal{H} = (X(\mathcal{H}), \mathcal{E}(\mathcal{H}))$ be a connected hypergraph with $|\mathcal{E}(\mathcal{H})|\geq 1$ and $t_p(\mathcal{H})$ be the number of pendant edges in $\mathcal{H}$. Then, $rc(\mathcal{H})\geq \max\{diam(\mathcal{H}), t_p(\mathcal{H})\}$.

Carpentier et al. ^[23] have also obtained the rainbow connection number of a minimally connected hypergraph. A minimally connected hypergraph is a connected hypergraph $\mathcal{H}$ with $|\mathcal{E}(\mathcal{H})|\geq 1$, where $\mathcal{H}-\{E\}$ is disconnected for every $E\in \mathcal{E}(\mathcal{H})$. The rainbow connection number of a minimally connected hypergraph is stated in the following theorem:

Theorem 1.1. ^[23] Let $\mathcal{H}$ be a connected hypergraph with $|\mathcal{E}(\mathcal{H})|\geq 1$. Then, $rc(\mathcal{H}) = |\mathcal{E}(\mathcal{H})|$ if and only if $\mathcal{H}$ is minimally connected.

In addition, they also obtained the rainbow connection number of an $r$-uniform cycle hypergraph, an $r$-uniform complete hypergraph, and an $r$-uniform complete multipartite hypergraph. Since the rainbow connection concept has not been applied to $r$-uniform hypertrees, we apply it in this article.

For $r\geq 2$, $1\leq s < r$, and $t\geq 1$, an $s$-overlapping $r$-uniform hypergraph with size $t$ is $r$-uniform connected hypergraph, with $s$ being the maximum cardinality of the vertex set obtained from the intersection of each pair of edges. The collection of $s$-overlapping $r$-uniform hypergraphs with size $t$ is denoted by $\mathfrak{H}_{s, t}^r$. As an example element of $\mathfrak{H}_{s, t}^r$ is a hypergraph $\mathcal{H} = (X(\mathcal{H}), \mathcal{E}(\mathcal{H}))$ with the vertex set $X(\mathcal{H}) = \{v_1, v_2, v_3, v_4, v_5, v_6\}$ and the edge set $\mathcal{E}(\mathcal{H}) = \{E_1, E_2, E_3, E_4\}$, where $E_1 = \{v_1, v_2, v_3\}$, $E_2 = \{v_2, v_3, v_4\}$, $E_3 = \{v_2, v_5, v_6\}$, and $E_4 = \{v_4, v_5, v_6\}$. This hypergraph is a 2-overlapping 3-uniform hypergraph with size 4 because the maximum cardinality of the vertex set obtained from the intersection of each pair of edges is 2. By adopting the definition of $\mathfrak{H}_{s, t}^r$, we define an $s$-overlapping $r$-uniform hypertree with size $t$, denoted by $\mathcal{T}_{s, t}^r$, as an $r$-uniform connected hypertree, with $s$ being the maximum cardinality of the vertex set obtained from the intersection of each pair of edges in $\mathcal{T}_{s, t}^r$.

2.   Main results

In this section, we determine the rainbow connection numbers of six classes of $s$-overlapping $r$-uniform hypertrees with size $t$. They are $s$-overlapping $r$-uniform hyperpaths, hyperstars, broom hypergraphs, double-homogeneous star hypergraphs, homogeneous caterpillar hypergraphs, and homogeneous centipede hypergraphs with size $t$. For simplification, we define $[a, b] = \{\theta\in \mathbb{Z}| a\leq \theta\leq b\}$. Let $x$ and $y$ be two natural numbers. We define

2.1.   Rainbow connection number of an $s$-overlapping $r$-uniform hyperpath with size $t$

The definition of an $s$-overlapping $r$-uniform hyperpath with size $t$ is as follows:

Definition 2.1. Let $r$, $s$, and $t$ be three integers with $r\geq 2$, $1\leq s < r$, and $t\geq 1$. An $s$-overlapping $r$-uniform hyperpath with size $t$, denoted by $\mathcal{P}_{s, t}^r$, is a connected hypergraph that has the vertex set ${X(\mathcal{P}_{s, t}^r) = \{v_1, v_2, \ldots, v_{(t-1)(r-s)+r}\}}$ and the edge set $\mathcal{E}(\mathcal{P}_{s, t}^r) = \{E_1, E_2, \ldots, E_t\}$ with

It is obvious that $diam(\mathcal{P}_{s, 1}^r) = 1$ and $diam(\mathcal{P}_{s, 2}^r) = 2$. To determine the diameter of $\mathcal{P}_{s, t}^r$ with size $t\geq 3$, we need the following Lemma 2.1:

Lemma 2.1. ^[33] Every connected $r$-uniform hypergraph contains a spanning minimally connected subhypergraph.

Any hypergraph $\mathcal{H}' = (X'(\mathcal{H}'), \mathcal{E}'(\mathcal{H}'))$ is referred to as a subhypergraph of $\mathcal{H}$ if $X'(\mathcal{H}')\subseteq X(\mathcal{H})$ and ${\mathcal{E}'(\mathcal{H}')\subseteq \mathcal{E}(\mathcal{H})}$. Then, the diameter of an $s$-overlapping $r$-uniform hyperpath with size $t\geq 3$ is as follows:

Lemma 2.2. Let $r$, $s$, and $t$ be three integers with $r\geq 2$, $1\leq s < r$, and $t\geq 3$. The diameter of an $s$-overlapping $r$-uniform hyperpath with size $t$ is $diam(\mathcal{P}_{s, t}^r) = {\left\lceil\frac{t(r-s)+s-a}{r-a}\right\rceil}$, where $a = r{\rm \; mod^*\; }(r-s)$.

Proof. Let $\mathcal{P}_{s, t}^r = (X(\mathcal{P}_{s, t}^r), \mathcal{E}(\mathcal{P}_{s, t}^r))$ be an $s$-overlapping $r$-uniform hyperpath with size $t$. Since $\mathcal{P}_{s, t}^r$ is an $r$-uniform connected hypergraph, by Lemma 2.1, $\mathcal{P}_{s, t}^r$ contains a spanning minimally connected subhypergraph. Next, we construct a spanning minimally connected subhypergraph that is formed from the edges connecting the first and last edges of $\mathcal{P}_{s, t}^r$. In this case, every two consecutive edges intersect as many as $r{\rm \; mod^*\; }(r-s)$ vertices, except the intersecting of the last two edges is a maximum of $s$ vertices. Let $a = r{\rm \; mod^*\; }(r-s)$, $b = \frac{r-a}{r-s}$, and $M$ be a spanning subhypergraph of $\mathcal{P}_{s, t}^r$, where the edge set of $M$ is

It is easy to check that $M$ is a spanning minimally connected subhypergraph of $\mathcal{P}_{s, t}^r$. Since the order of $\mathcal{P}_{s, t}^r$ is $(t-1)(r-s)+r$ and the size of $M$ is $\left\lceil\frac{|X(M)|-a}{r-a}\right\rceil$, we get $diam(\mathcal{P}_{s, t}^r) = {\left\lceil\frac{t(r-s)+s-a}{r-a}\right\rceil}$. □

Let $n = |X(\mathcal{P}_{s, t}^r)| = (t-1)(r-s)+r$. If $s = r-1$, then $\mathcal{P}_{s, t}^r$ is called a tight $r$-uniform hyperpath with order $n$, denoted by $\mathcal{P}_n^r$ ^[34]. In this case, a tight 2-uniform hyperpath is a path graph. We know that the diameter of a path graph is $n-1$. Therefore, by Lemma 2.2, we get the following corollary:

Corollary 2.1. Let $r$ and $n$ be two integers with $2\leq r < n$. The diameter of a tight $r$-uniform hyperpath with order $n$ is $diam(\mathcal{P}_n^r) = {\left\lceil\frac{n-1}{r-1}\right\rceil}$.

By Carpentier et al.^[23], we have known the rainbow connection number of a minimally connected hypergraph. In the following, we provide the rainbow connection number of all $s$-overlapping $r$-uniform hyperpaths with size $t$, including a not minimally connected hyperpath.

By definition, $\mathcal{P}_{s, 1}^r$ and $\mathcal{P}_{s, 2}^r$ are minimally connected hypergraphs. Therefore, by Theorem 1.1, we have $rc(\mathcal{P}_{s, 1}^r) = 1$ and $rc(\mathcal{P}_{s, 2}^r) = 2$. The following is the rainbow connection number of $\mathcal{P}_{s, t}^r$ for $t\geq 3$.

Theorem 2.1. Let $r$, $s$, and $t$ be three integers with $r\geq 2$, $1\leq s < r$, and $t\geq 3$. The rainbow connection number of an $s$-overlapping $r$-uniform hyperpath with size $t$ is $rc(\mathcal{P}_{s, t}^r) = diam(\mathcal{P}_{s, t}^r)$.

Proof. Let $a = r{\rm \; mod^*\; }(r-s)$. For $r-s\geq \frac{r}{2}$, we obtain that $\mathcal{P}_{s, t}^r$ is a minimally connected hypergraph. Therefore, by Theorem 1.1, we have $rc(\mathcal{P}_{s, t}^r) = t$. Now, we show that $diam(\mathcal{P}_{s, t}^r) = t$. The shortest path connecting two vertices $v_1$ and $v_{(t-1)(r-s)+r}$ is $v_1E_1-E_2-\ldots-E_{t-1}-E_tv_{(t-1)(r-s)+r}$. Therefore, the diameter of $\mathcal{P}_{s, t}^r$ is the number of edges in $\mathcal{P}_{s, t}^r$. Thus, $diam(\mathcal{P}_{s, t}^r) = t$. Hence, $rc(\mathcal{P}_{s, t}^r) = diam(\mathcal{P}_{s, t}^r)$.

For $r-s < \frac{r}{2}$, by the inequality (1.1), we have $rc(\mathcal{P}_{s, t}^r)\geq diam(\mathcal{P}_{s, t}^r)$. Now, we show that $rc(\mathcal{P}_{s, t}^r)\leq diam(\mathcal{P}_{s, t}^r)$. By Lemma 2.2, we get $diam(\mathcal{P}_{s, t}^r) = {\left\lceil\frac{t(r-s)+s-a}{r-a}\right\rceil}$. We define an edge coloring $c:\mathcal{E}(\mathcal{P}_{s, t}^r)\rightarrow \left\{1, 2, \ldots, {\left\lceil\frac{t(r-s)+s-a}{r-a}\right\rceil}\right\}$ as $c(E_i) = {\left\lceil\frac{i(r-s)+s-a}{r-a}\right\rceil}$ for $i\in [1, t]$. By the edge coloring $c$, we show that for any two vertices, $v_i$ and $v_j$ in $X(\mathcal{P}_{s, t}^r)$ there exists a $v_i$-$v_j$ rainbow path. It is trivial for two adjacent vertices, $v_i$ and $v_j$. Now, we consider the cases where $v_i$ and $v_j$ are not adjacent. For $1\leq i < j\leq (t-1)(r-s)+r$, let $p = \left\lceil\frac{i}{r-s}\right\rceil$, $b = \frac{r-a}{r-s}$, $k = \left\lceil\frac{p(r-s)+s-a}{r-a}\right\rceil$, $D = diam(\mathcal{P}_{s, t}^r)$, and $d = d(v_i, v_j) = \left\lceil\frac{j-i-a+i{\rm \; mod^*\; } (r-s)}{r-a}\right\rceil$. To simplify the writing of the formula, let $\hat{d} = d-1$, $\gamma_1 = (p+(D-k)b-1)(r-s)+r$, and $\gamma_2 = (p+(D-k-1)b-1)(r-s)+r$. Then, we show a $v_i$-$v_j$ rainbow path in the following cases:

Case 1. If $b\mid (t-1)$, then a $v_i$-$v_j$ rainbow path is

Case 2. If $b\nmid (t-1)$, then a $v_i$-$v_j$ rainbow path is

Therefore, we get $rc(\mathcal{P}_{s, t}^r)\leq \left\lceil\frac{t(r-s)+s-a}{r-a}\right\rceil$. Hence, $rc(\mathcal{P}_{s, t}^r)\leq diam(\mathcal{P}_{s, t}^r)$. Thus, we conclude that $rc(\mathcal{P}_{s, t}^r) = diam(\mathcal{P}_{s, t}^r)$. □

For illustration of Theorem 2.1, we give two examples of a rainbow connected coloring of $\mathcal{P}_{1, 3}^3$ and $\mathcal{P}_{4, 11}^5$ in the following Figures 1(a) and 1(b), respectively. We know that $\mathcal{P}_{1, 3}^3$ is a minimally connected hypergraph with $rc(\mathcal{P}_{1, 3}^3) = 3$, whereas $\mathcal{P}_{4, 11}^5$ is not a minimally connected hypergraph with $rc(\mathcal{P}_{4, 11}^5) = 4$.

If $s = 1$, then $\mathcal{P}_{s, t}^r$ is called a loose $r$-uniform hyperpath ^[34]. Figures 1(a) and 1(b) are also illustrations of loose and tight $r$-uniform hyperpaths, respectively. By Theorem 2.1, we obtain the rainbow connection number of a tight $r$-uniform hyperpath with order $n$ as follows:

Corollary 2.2. Let $r$ and $n$ be two integers with $2\leq r < n$. The rainbow connection number of a tight $r$-uniform hyperpath with order $n$ is $rc(\mathcal{P}_n^r) = diam(\mathcal{P}_n^r)$.

2.2.   Rainbow connection number of an $s$-overlapping $r$-uniform hyperstar with size $t$

In the following, we define an $s$-overlapping $r$-uniform hyperstar with size $t$.

Definition 2.2. Let $r$, $s$, and $t$ be three integers with $r\geq 2$, $1\leq s < r$, and $t\geq 1$. An $s$-overlapping $r$-uniform hyperstar with size $t$, denoted by $\mathcal{S}_{s, t}^r$, is a connected hypergraph that has the vertex set $X(\mathcal{S}_{s, t}^r) = \{v_1, v_2, \ldots, v_{t(r-s)+s}\}$ and the edge set $\mathcal{E}(\mathcal{S}_{s, t}^r) = \{E_1, E_2, \ldots, E_t\}$ with

By definition, $\mathcal{S}_{s, t}^r$ is a minimally connected hypergraph. Since $|\mathcal{E}(\mathcal{S}_{s, t}^r)| = t$, by Theorem 1.1, we get $rc(\mathcal{S}_{s, t}^r) = t$. We can see that every edge of an $s$-overlapping $r$-uniform hyperstar with size $t$ is a pendant edge. Therefore, if $t_p(\mathcal{S}_{s, t}^r)$ is the number of pendant edges of $\mathcal{S}_{s, t}^r$, then we obtain the following corollary:

Corollary 2.3. Let $r$, $s$, and $t$ be three integers with $r\geq 2$, $1\leq s < r$, and $t\geq 1$, and let $\mathcal{S}_{s, t}^r$ be an $s$-overlapping $r$-uniform hyperstar with size $t$. If $t_p(\mathcal{S}_{s, t}^r)$ is the number of pendant edges of $\mathcal{S}_{s, t}^r$, then the rainbow connection number of $\mathcal{S}_{s, t}^r$ is $rc(\mathcal{S}_{s, t}^r) = t_p(\mathcal{S}_{s, t}^r)$.

For illustration, we give an example of a rainbow connected coloring of $\mathcal{S}_{3, 6}^5$ in the following Figure 2. The rainbow connection number of $\mathcal{S}_{3, 6}^5$ is 6.

2.3.   Rainbow connection number of an $s$-overlapping $r$-uniform broom hypergraph with size $y+w$

An $s$-overlapping $r$-uniform broom hypergraph with size $y+w$ is a connected hypergraph formed from an $s$-overlapping $r$-uniform hyperpath with size $y$ ($\mathcal{P}_{s, y}^r$) and $w$ pendant edges attached to the vertex set obtained from the intersection of the first edge and the second edge $\mathcal{P}_{s, y}^r$. We call an $s$-overlapping $r$-uniform hyperpath with size $y$ as the broomstick and $w$ pendant edges as sticks. An $s$-overlapping $r$-uniform broom hypergraph with size $y+w$ is one of the classes in the collection of $s$-overlapping $r$-uniform hypergraphs with size $t$, where $t = y+w$. In detail, the following is the definition of an $s$-overlapping $r$-uniform broom hypergraph with size $y+w$.

Definition 2.3. Let $r$, $s$, $y$, and $w$ be four integers with $r\geq 2$, $1\leq s < r$, $y\geq 2$, and $w\geq 1$. An $s$-overlapping $r$-uniform broom hypergraph with size $y+w$, denoted by $\mathcal{BR}_{s, y, w}^r$, is a connected hypergraph that has the vertex set $X(\mathcal{BR}_{s, y, w}^r) = \{v_1, v_2, \ldots, v_{(y+w-1)(r-s)+r}\}$ and the edge set $\mathcal{E}(\mathcal{BR}_{s, y, w}^r) = \{E_1, E_2, \ldots, E_i, \ldots, E_{y}\}\cup\{E_{y+1}, E_{y+2}, \ldots, E_j, \ldots, E_{y+w}\}$ with

where $n^* = (y-1)(r-s)+r$.

By Definition 2.3, $E_i$ for every $i\in [1, y]$ is an edge of the broomstick. Meanwhile, $E_j$ for every $j\in [y+1, y+w]$ is a stick. It is easy to check that the diameter of $\mathcal{BR}_{s, y, w}^r$ is the same as the diameter of $\mathcal{P}_{s, y}^r$.

First, we consider $\mathcal{BR}_{s, y, w}^r$ with size $y = 2$. For $w\geq 1$, it is an $s$-overlapping $r$-uniform hyperstar with size $y+w$. Hence, we get $rc(\mathcal{BR}_{s, y, w}^r) = y+w$. Now, we determine the rainbow connection number of $\mathcal{BR}_{s, y, w}^r$ with size $y\geq 3$ as follows:

Theorem 2.2. Let $r$, $s$, $y$, and $w$ be four integers with $r\geq 2$, $1\leq s < r$, $y\geq 3$, and $w\geq 1$. The rainbow connection number of an $s$-overlapping $r$-uniform broom hypergraph with size $y+w$ is

Proof. Let $\mathcal{BR}_{s, y, w}^r = (X(\mathcal{BR}_{s, y, w}^r), \mathcal{E}(\mathcal{BR}_{s, y, w}^r))$ be an $s$-overlapping $r$-uniform broom hypergraph with size $y+w$. Therefore, we consider two cases.

Case 1. $r-s\geq \frac{r}{2}$

By definition, $\mathcal{BR}_{s, y, w}^r$ is a minimally connected hypergraph. Therefore, by Theorem 1.1, we get $rc(\mathcal{BR}_{s, y, w}^r) = y+w$. Now, we show that $y = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil$. Since $r-s = \frac{r}{2}$ and $a = r{\rm\; mod^*\; }(r-s)$, we get $a = s$, so $r-a = r-s$. Therefore, we obtain that $y = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil$. For $r-s > \frac{r}{2}$, we have that every edge of $\mathcal{BR}_{s, y, w}^r$ is a pendant edge. Since $\mathcal{BR}_{s, y, w}^r$ is formed from one $\mathcal{P}_{s, y}^r$ and $w$ pendant edges, we have every edge of $\mathcal{P}_{s, y}^r$ is a pendant edge. By the definition of $\mathcal{P}_{s, y}^r$, the number of edges and vertices is $y$ and $(y-1)(r-s)+r$, respectively. Therefore, we obtain that the number of pendant edges of $\mathcal{P}_{s, y}^r$ is $\left\lceil\frac{(y-1)(r-s)+r-a}{r-a}\right\rceil$. Hence, $y = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil$. Thus, we get $rc(\mathcal{BR}_{s, y, w}^r) = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil+w$.

Case 2. $r-s < \frac{r}{2}$

We show that $rc(\mathcal{BR}_{s, y, w}^r)\geq {\left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil}+w$. Since $\mathcal{BR}_{s, y, w}^r$ formed from one $\mathcal{P}_{s, y}^r$ and $w$ pendant edges, at least the rainbow connection numbers of $\mathcal{BR}_{s, y, w}^r$ are the sum of the rainbow connection numbers of $\mathcal{P}_{s, y}^r$ and $w$. By Theorem 2.1 and Lemma 2.2, $rc(\mathcal{P}_{s, y}^r) = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil$. Hence, we get $rc(\mathcal{BR}_{s, y, w}^r)\geq {\left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil}+w$.

Now, we show that $rc(\mathcal{BR}_{s, y, w}^r)\leq {\left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil}+w$ by defining an edge coloring $c:\mathcal{E}(\mathcal{BR}_{s, y, w}^r)\rightarrow \left\{1, 2, \ldots, {\left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil}+w\right\}$ as follows:

Let $n^* = (y-1)(r-s)+r$ and $b = \frac{r-a}{r-s}$. In the proof of Theorem 2.1, we showed that there exists a $v_i$-$v_j$ rainbow path for $1\leq i < j\leq (y-1)(r-s)+r$. Now, we show that there exists a $v_i$-$v_j$ rainbow path for other $i$ and $j$. It is trivial for two adjacent vertices, $v_i$ and $v_j$. We consider the subcases where $v_i$ and $v_j$ are not adjacent as follows:

Subcase 2.1. $1\leq i\leq r-s$ and $n^*+1\leq j \leq n^*+w(r-s)$

In this case, the vertices $v_i$ and $v_j$ are the pendant vertices on the pendant edge. Therefore, by edge coloring $c$, every pendant edge has a distinct color, so that there is a $v_i$-$v_j$ rainbow path with length 2. The same reasoning applies to $n^*+1\leq i < j\leq n^*+w(r-s)$.

Subcase 2.2. $r+1\leq i\leq n^*$ and $n^*+1\leq j\leq n^*+w(r-s)$

If $(r-s)\mid r$, then the distance of two vertices $v_i$ and $v_j$ is $d(v_i, v_j) = \left\lceil\frac{i-1}{r-a}\right\rceil$. If $(r-s)\nmid r$, then $d(v_i, v_j) = \left\lceil\frac{i-a}{r-a}\right\rceil$. Let $d = d(v_i, v_j)$, $p = \left\lceil\frac{i}{r-s}\right\rceil$, $q = y+\left\lceil\frac{j-n^*}{r-s}\right\rceil$, and $b = \frac{r-a}{r-s}$. For every two vertices $v_i$ and $v_j$, there is a $v_i$-$v_j$ rainbow path in the following form:

Therefore, we get $rc(\mathcal{BR}_{s, y, w}^r)\leq \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil+w$.

Thus, we conclude that $rc(\mathcal{BR}_{s, y, w}^r) = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil+w$.

□

For illustration of Theorem 2.2, we provide two examples of a rainbow connected coloring of $\mathcal{BR}_{1, 5, 2}^3$ and $\mathcal{BR}_{2, 7, 2}^3$ in the following Figures 3(a) and 3(b), respectively. We know that $\mathcal{BR}_{1, 5, 2}^3$ is a minimally connected hypergraph with $rc(\mathcal{BR}_{1, 5, 2}^3) = 7$, whereas $\mathcal{BR}_{2, 7, 2}^3$ is not a minimally connected hypergraph with $rc(\mathcal{BR}_{2, 7, 2}^3) = 6$.

2.4.   Rainbow connection number of an $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$

An $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$ is a connected hypergraph formed from an $s$-overlapping $r$-uniform broom hypergraph with size $y+w$ and $w$ pendant edges attached to the vertex set obtained from the intersection of the last edge and the edge before the last of the broomstick. Therefore, the number of sticks is $2w$. An $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$ is one of the classes in the collection of $s$-overlapping $r$-uniform hypergraphs with size $t$, where $t = y+2w$. The definition of an $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$ is as follows:

Definition 2.4. Let $r$, $s$, $y$, and $w$ be four integers with $r\geq 2$, $1\leq s < r$, $y\geq 3$, and $w\geq 1$. An $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$, denoted by $\mathcal{DS}_{s, y, w}^r$, is a connected hypergraph that has the vertex set $X(\mathcal{DS}_{s, y, w}^r) = \{v_1, v_2, \ldots, v_{(y+2w-1)(r-s)+r}\}$ and the edge set $\mathcal{E}(\mathcal{DS}_{s, y, w}^r) = \{E_1, E_2, \ldots, E_i, \ldots,$ $E_{y}\}\cup\{E_{y+1}, E_{y+2}, \ldots, E_j, \ldots, E_{y+w}\}\cup\{E_{y+w+1}, E_{y+w+2},$ $\ldots, E_k, \ldots, E_{y+2w}\}$ with

where $n^* = (y-1)(r-s)+r$.

By Definition 2.4, $E_i$ for every $i\in [1, y]$ is an edge of the broomstick. Meanwhile, $E_j$ for every $j\in [y+1, y+w]$ and $E_k$ for every $k\in [y+w+1, y+2w]$ is a stick. It is easy to check that the diameter of $\mathcal{DS}_{s, y, w}^r$ is the same as the diameter of $\mathcal{P}_{s, y}^r$ and $\mathcal{BR}_{s, y, w}^r$. Now, we determine the rainbow connection number of an $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$.

Theorem 2.3. Let $r$, $s$, $y$, and $w$ be four integers with $r\geq 2$, $1\leq s < r$, $y\geq 3$, and $w\geq 1$. The rainbow connection number of an $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$ is

where $a = r{\rm \; mod^*\; }(r-s)$.

Proof. Let $\mathcal{DS}_{s, y, w}^r = (X(\mathcal{DS}_{s, y, w}^r), \mathcal{E}(\mathcal{DS}_{s, y, w}^r))$ be an $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$. We consider two cases.

Case 1. $r-s\geq \frac{r}{2}$

According to Definition 2.4, there is not an $s$-overlapping $r$-uniform double-homogeneous star hypergraph with size $y+2w$ for $y < \frac{2r-s}{r-s}$. Therefore, we consider $\mathcal{DS}_{s, y, w}^r$ with $y\geq \frac{2r-s}{r-s}$. By definition, $\mathcal{DS}_{s, y, w}^r$ is a minimally connected hypergraph. Therefore, by Theorem 1.1, we get $\mathcal{DS}_{s, y, w}^r = y+2w$. Now, we show that $y = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil$. Since $\mathcal{DS}_{s, y, w}^r$ is formed from one $\mathcal{P}_{s, y}^r$ and $2w$ pendant edges, the proof of $y = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil$ is similar to the proof of Theorem 2.2 Case 1. Thus, we get $\mathcal{DS}_{s, y, w}^r = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil+2w$.

Case 2. $r-s < \frac{r}{2}$

We consider two subcases.

Subcase 2.1. $y < \frac{2r-s}{r-s}$

Since the diameter of $\mathcal{DS}_{s, y, w}^r$ is equal to the diameter of $\mathcal{P}_{s, y}^r$, we get $diam(\mathcal{DS}_{s, y, w}^r) = 2$. On the other side, since $y < \frac{2r-s}{r-s}$, we get an $s$-overlapping $r$-uniform double-homogeneous star hypergraph with every pair of pendant edges intersecting such that the number of pendant edges is $2w+2$. By Lemma 1.1, we obtain $rc(\mathcal{DS}_{s, y, w}^r)\geq 2w+2$. Next, since every vertex is contained in a pendant edge and each pendant edge has a distinct color, we get a $v_i$-$v_j$ rainbow path with length 2 for every $1\leq i < j\leq (y+2w-1)(r-s)+r$. Therefore, we get $rc(\mathcal{DS}_{s, y, w}^r)\leq 2w+2$. Thus, $rc(\mathcal{DS}_{s, y, w}^r) = 2w+2$.

Subcase 2.2. $y\geq \frac{2r-s}{r-s}$

Similar to the proof of the lower bound of the rainbow connection number in Case 2 of Theorem 2.2, we get $rc(\mathcal{DS}_{s, y, w}^r)\geq {\left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil}+2w$. Next, we show that $rc(\mathcal{DS}_{s, y, w}^r)\leq {\left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil}+2w$ by defining an edge coloring $c:\mathcal{E}(\mathcal{DS}_{s, y, w}^r)\rightarrow \left\{1, 2, \ldots, {\left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil}+2w\right\}$ as follows:

Let $n^* = (y-1)(r-s)+r$ and $b = \frac{r-a}{r-s}$. It is trivial for two adjacent vertices, $v_i$ and $v_j$. Now, we consider the subsubcases where $v_i$ and $v_j$ are not adjacent. In the proof of Theorem 2.1, we show that there exists a $v_i$-$v_j$ rainbow path for $1\leq i < j\leq (y-1)(r-s)+r$. In the proof of Theorem 2.2, we show that there exists a $v_i$-$v_j$ rainbow path for

(1) $1\leq i\leq r-s$ and $n^*+1\leq j \leq n^*+w(r-s)$,

(2) $n^*+1\leq i < j\leq n^*+w(r-s)$,

(3) $r+1\leq i\leq n^*$ and $n^*+1\leq j\leq n^*+w(r-s)$.

By using the same reasoning as Theorem 2.2 in Subcase 2.1, we show a $v_i$-$v_j$ rainbow path for

(1) $n^*-(r-s-1)\leq i\leq n^*$ and $n^*+w(r-s)+1\leq j \leq n^*+2w(r-s)$,

(2) $n^*+w(r-s)+1\leq i < j\leq n^*+2w(r-s)$.

Next, we show a $v_i$-$v_j$ rainbow path for other $i$ and $j$ as follows:

Subsubcase 2.2.1. $1\leq i \leq n^*-r$ and $n^*+w(r-s)+1\leq j\leq n^*+2w(r-s)$

If $(r-s)\mid r$, then the distance between two vertices $v_i$ and $v_j$ is $d(v_i, v_j) = \left\lceil\frac{n^*-i}{r-a}\right\rceil$. If $(r-s)\nmid r$, then $d(v_i, v_j) = \left\lceil\frac{n^*-i-a+i{\rm \; mod^*\; } (r-s)}{r-a}\right\rceil$. Let $d = d(v_i, v_j)$, $p = \left\lceil\frac{i}{r-s}\right\rceil$, $q = y+\left\lceil\frac{j-n^*}{r-s}\right\rceil$, and $b = \frac{r-a}{r-s}$. For every two vertices $v_i$ and $v_j$, we get $v_iE_p-E_{p+b}-E_{p+2b}-\ldots-E_{p+(d-2)b}-E_qv_j$ as a $v_i$-$v_j$ rainbow path.

Subsubcase 2.2.2. $n^*+1\leq i\leq n^*+w(r-s)$ and $n^*+w(r-s)+1\leq j \leq n^*+2w(r-s)$

The distance between two vertices $v_i$ and $v_j$ is $diam(\mathcal{DS}_{s, y, w}^r) = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil$. Let $D = diam(\mathcal{DS}_{s, y, w}^r)$, $q_1 = y+\left\lceil\frac{i-n^*}{r-s}\right\rceil$, $q_2 = y+\left\lceil\frac{j-n^*}{r-s}\right\rceil$, and $b = \frac{r-a}{r-s}$. For every two vertices $v_i$ and $v_j$, we get $v_iE_{q_1}-E_{1+b}-E_{1+2b}-\ldots-E_{1+(D-2)b}-E_{q_2}v_j$ as a $v_i$-$v_j$ rainbow path.

Therefore, we get $rc(\mathcal{DS}_{s, y, w}^r)\leq \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil+2w$.

Thus, we conclude that $rc(\mathcal{DS}_{s, y, w}^r) = \left\lceil\frac{y(r-s)+s-a}{r-a}\right\rceil+2w$. □

In the following Figure 4, we give an illustration of Theorem 2.3. Figures 4(a) and 4(b) are a rainbow connected coloring of $\mathcal{DS}_{1, 5, 2}^3$ and $\mathcal{DS}_{2, 7, 2}^3$, respectively. The hypergraph of $\mathcal{DS}_{1, 5, 2}^3$ is a minimally connected hypergraph with $rc(\mathcal{DS}_{1, 5, 2}^3) = 9$, whereas $\mathcal{DS}_{2, 7, 2}^3$ is not a minimally connected hypergraph with $rc(\mathcal{DS}_{2, 7, 2}^3) = 8$.

2.5.   Rainbow connection number of an $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $(z+1)w+z$

An $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $(z+1)w+z$ is a connected hypergraph formed from an $s$-overlapping $r$-uniform hyperpath with size $z$ $\mathcal{P}_{s, z}^r$ and $w$ pendant edges attached to the first edge, the last edge, and the vertex set from the intersection of any two consecutive edges in $\mathcal{P}_{s, z}^r$. We call the edge in $\mathcal{P}_{s, z}^r$ as a backbone, a pendant edge intersection with the set of vertices obtained from the intersection of any two edges in $\mathcal{P}_{s, z}^r$ as a leg base, and a pendant edge that is not a subhypergraph of $\mathcal{P}_{s, z}^r$ as a leg. Therefore, we have $z+1$ leg bases and $w$ legs. An $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $(z+1)w+z$ is one of the classes in the collection of $s$-overlapping $r$-uniform hypergraphs with size $t$, where $t = (z+1)w+z$. In detail, the following is the definition of an $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $(z+1)w+z$.

Definition 2.5. Let $r$, $s$, $z$, and $w$ be four integers with $r\geq 2$, $1\leq s < r$, $z\geq 1$, and $w\geq 1$. An $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $(z+1)w+z$, denoted by $\mathcal{HC}_{s, z, w}^r$, is a connected hypergraph that has the vertex set $X(\mathcal{HC}_{s, z, w}^r) = \{v_1, v_2, \ldots, v_{(z-1)(r-s)+r}\}\cup \{u_{\alpha, \beta}^1, u_{\alpha, \beta}^2, \ldots, u_{\alpha, \beta}^{r-s}\}$ for every $\alpha \in [1, z+1]$ and $\beta \in [1, w]$ and the edge set $\mathcal{E}(\mathcal{HC}_{s, z, w}^r) = \{E_i|{i\in [1, z]}\}\cup \{E_{\alpha, \beta}|\alpha \in [1, z+1], \beta \in [1, w]\}$ with

By Definition 2.5, $E_i$ for every $i\in [1, z]$ is an edge of the backbone. Meanwhile, $E_{\alpha, \beta}$ for every $\alpha \in [1, z+1]$, $\beta \in [1, w]$ is a leg. For an example, consider an $2$-overlapping $3$-uniform homogeneous caterpillar hypergraph with size 9 in Figure 5(b), denoted by $\mathcal{HC}_{2, 4, 1}^3$. We can see that the hypergraph has $5$ leg bases and $1$ leg for every leg bases. In detail, the hypergraph has $X(\mathcal{HC}_{2, 4, 1}^3) = \{v_1, v_2, v_3, v_4, v_5, v_6\}\cup \{u_{1, 1}^1\}\cup, \{u_{2, 1}^1\}\cup \{u_{3, 1}^1\} \cup \{u_{4, 1}^1\} \cup \{u_{5, 1}^1\}$ and $\mathcal{E}(\mathcal{HC}_{2, 4, 1}^3) = \{E_1, E_2, E_3, E_4\}\cup \{E_{1, 1}, E_{2, 1}, E_{3, 1}, E_{4, 1}, E_{5, 1}\}$ where $E_1 = \{v_1, v_2, v_3\}$, $E_2 = \{v_2, v_3, v_4\}$, $E_3 = \{v_3, v_4, v_5\}$, $E_4 = \{v_4, v_5, v_6\}$, $E_{1, 1} = \{v_1, v_2\}\cup \{u_{1, 1}^1\}$, $E_{2, 1} = \{v_2, v_3\}\cup \{u_{2, 1}^1\}$, $E_{3, 1} = \{v_3, v_4\}\cup \{u_{3, 1}^1\}$, $E_{4, 1} = \{v_4, v_5\}\cup \{u_{4, 1}^1\}$, $E_{5, 1} = \{v_5, v_6\}\cup \{u_{5, 1}^1\}$.

Now, we show the rainbow connection number of an $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $(z+1)w+z$ as follows:

Theorem 2.4. Let $r$, $s$, $z$, and $w$ be four integers with $r\geq 2$, $1\leq s < r$, $z\geq 1$, and $w\geq 1$. The rainbow connection number of an $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $(z+1)w+z$ is

Proof. Let $\mathcal{HC}_{s, z, w}^r = (X(\mathcal{HC}_{s, z, w}^r), \mathcal{E}(\mathcal{HC}_{s, z, w}^r)$ be an $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $(z+1)w+z$. We consider two cases.

Case 1. $r-s\geq \frac{r}{2}$

By definition, $\mathcal{HC}_{s, z, w}^r$ is a minimally connected hypergraph. Therefore, by Theorem 1.1, $rc(\mathcal{HC}_{s, z, w}^r) = |\mathcal{E}(\mathcal{HC}_{s, z, w}^r)| = (z+1)w+z$.

Case 2. $r-s < \frac{r}{2}$

By definition, $\mathcal{HC}_{s, z, w}^r$ is not a minimally connected hypergraph. First, we show the lower bound of $rc(\mathcal{HC}_{s, z, w}^r)$. For $z\geq 1$, we get $diam(\mathcal{HC}_{s, z, w}^r)\leq t_p(\mathcal{HC}_{s, z, w}^r)$. Since every pendant edge has a distinct color, we get $(z+1)w$ colors. By Lemma 1.1, we obtain $rc(\mathcal{HC}_{s, z, w}^r)\geq (z+1)w$. Next, we determine the upper bound of $rc(\mathcal{HC}_{s, z, w}^r)$. We define an edge coloring $c: \mathcal{E}(\mathcal{HC}_{s, z, w}^r)\rightarrow \{1, 2, \ldots, (z+1)w\}$ as follows:

It is trivial for two adjacent vertices, $v_i$ and $v_j$. We consider the cases where $v_i$ and $v_j$ are not adjacent. Since each pendant edge is assigned a distinct color, we can show a $u$-$v$ rainbow path for any pair of vertices $u$ and $v$ in $X(\mathcal{HC}_{s, z, w}^r)$. For every two vertices $u$ and $v$, there exists a $u$-$v$ rainbow path of the form $uE_{\alpha, \beta}-E_{\alpha+1, \beta}-E_{\alpha+2, \beta}, \ldots, E_{\alpha+\ell, \beta}v$, where $\ell+1$ is the number of pendant edges. Therefore, we get $rc(\mathcal{HC}_{s, z, w}^r)\leq (z+1)w$. Thus, we conclude that $rc(\mathcal{HC}_{s, z, w}^r) = (z+1)w$. □

For illustration of Theorem 2.4, we give two examples of a rainbow connected coloring of $\mathcal{HC}_{1, 4, 2}^3$ and $\mathcal{HC}_{2, 4, 1}^3$ in the following Figures 5(a) and 5(b), respectively. The hypergraph of $\mathcal{HC}_{1, 4, 2}^3$ is a minimally connected hypergraph with $rc(\mathcal{HC}_{1, 4, 2}^3) = 14$, whereas $\mathcal{HC}_{2, 4, 1}^3$ is not a minimally connected hypergraph with $rc(\mathcal{HC}_{2, 4, 1}^3) = 5$.

2.6.   Rainbow connection number of an $s$-overlapping $r$-uniform homogeneous centipede hypergraph with size $(z+1)w+z+2$

An $s$-overlapping $r$-uniform homogeneous centipede hypergraph with size $(z+1)w+z+2$ is a connected hypergraph formed from an $s$-overlapping $r$-uniform homogeneous caterpillar with size $(z+1)w+z$ $\mathcal{HC}_{s, z, w}^r$ and one pendant edge attached to the first edge of the backbone and one pendant edge attached to the last edge of the backbone. We refer to the two pendant edges added as a head and a tail, respectively. An $s$-overlapping $r$-uniform homogeneous centipede hypergraph with size $(z+1)w+z+2$ is one of the classes in the collection of $s$-overlapping $r$-uniform hypergraph with size $t$, where $t = (z+1)w+z+2$. Next, we define an $s$-overlapping $r$-uniform homogeneous centipede hypergraph with size $(z+1)w+z+2$ as follows:

Definition 2.6. Let $r$, $s$, $z$, and $w$ be four integers with $r\geq 2$, $1\leq s < r$, $z\geq 1$, and $w\geq 1$. An $s$-overlapping $r$-uniform homogeneous centipede hypergraph with size $(z+1)w+z+2$, denoted by $\mathcal{CP}_{s, z, w}^r$, is a connected hypergraph that has the vertex set $X(\mathcal{CP}_{s, z, w}^r) = \{v_1, v_2, \ldots, v_{(z+1)(r-s)+r}\}\cup \{u_{\alpha, \beta}^1, u_{\alpha, \beta}^2, \ldots, u_{\alpha, \beta}^{r-s}\}$ for every $\alpha \in [1, z+1]$ and $\beta \in [1, w]$, and the edge set $\mathcal{E}(\mathcal{HC}_{s, z, w}^r) = \{E_i|i\in [1, z+2]\}\cup \{E_{\alpha, \beta}|\alpha \in [1, z+1], \beta \in [1, w]\}$ with

By Definition 2.6, $E_i$ for every $i\in [2, z+1]$ is an edge of the backbone. Meanwhile, $E_1$ and $E_{z+2}$ are the head and the tail, respectively. In addition, $E_{\alpha, \beta}$ for every $\alpha \in [1, z+1]$ and $\beta \in [1, w]$ is a leg.

Since $\mathcal{CP}_{s, z, w}^r$ are $\mathcal{HC}_{s, z, w}^r$ which added one pendant edge on the first edge and the last edge of the backbone, and each pendant edge is assigned a distinct color, we get $rc(\mathcal{CP}_{s, z, w}^r) = rc(\mathcal{HC}_{s, z, w}^r)+2$. Therefore, we obtain the rainbow connection number of an $s$-overlapping $r$-uniform homogeneous centipede hypergraph with size $(z+1)w+z+2$ as follows:

Corollary 2.4. Let $r$, $s$, $z$, and $w$ be four integers with $r\geq 2$, $1\leq s < r$, $z\geq 1$, and $w\geq 1$. The rainbow connection number of an $s$-overlapping $r$-uniform homogeneous centipede hypergraph with size $(z+1)w+z+2$ is

In the following Figure 6, we give an illustration of Corollary 2.4. Figures 6(a) and 6(b) are a rainbow connected coloring of $\mathcal{CP}_{1, 4, 2}^3$ and $\mathcal{CP}_{2, 4, 1}^3$, respectively. We know that $\mathcal{CP}_{1, 4, 2}^3$ is a minimally connected hypergraph with $rc(\mathcal{CP}_{1, 4, 2}^3) = 16$, whereas $\mathcal{CP}_{2, 4, 1}^3$ is not a minimally connected hypergraph with $rc(\mathcal{CP}_{2, 4, 1}^3) = 7$.

3.   Conclusions and open problems

We obtained the rainbow connection numbers of six classes of $s$-overlapping $r$-uniform hypertrees with size $t$. If $r = 2$, then we confirm that the rainbow connection numbers of them are equal to the rainbow connection numbers of trees which have been obtained by Chartrand et al.^[2]. Moreover, we provided the best lower bound of the rainbow connection numbers of $s$-overlapping $r$-uniform hypertrees with size $t$, namely their diameter or their number of pendant edges. We have shown that the rainbow connection number of an $s$-overlapping $r$-uniform hyperpath with size $t$ equals to its diameter. Meanwhile, the rainbow connection number of $\mathcal{T}_{s, t}^r$ equals its number of pendant edges if $\mathcal{T}_{s, t}^r$ is an $s$-overlapping $r$-uniform homogeneous caterpillar hypergraph with size $t$ for $r-s < \frac{r}{2}$, an $s$-overlapping $r$-uniform homogeneous centipede hypergraph with size $t$ for $r-s < \frac{r}{2}$, or an $s$-overlapping $r$-uniform hyperstar with size $t$. This research can be continued by determining the rainbow connection numbers of other classes of $s$-overlapping $r$-uniform hypergraphs with size $t$ where the rainbow connection numbers of their host graphs have been obtained. In addition, there is the issue of determining the best upper bound for the rainbow connection numbers of non-minimally connected hypergraphs.

Author contributions

Sitta Alief Farihati, A. N. M. Salman and Pritta Etriana Putri: Conceptualization, Investigation, Methodology, Supervision, Validation, Visualization, Writing-original draft, Writing-review & editing. All authors of this article have been contributed equally. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

We want to thank Universitas Terbuka for the study's financial support. We thank Indonesia's Ministry of Education and Culture for doctoral dissertation research grant.

Conflict of interest

All authors declare no conflicts of interest in this article.