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

Abstract

The rainbow connection concept was developed to determine the minimum number of passwords required to exchange encrypted information between two agents. If the information exchange involves divisions managing more than two agents, the rainbow connection concept can be extended to a hypergraph. In 2014, Carpentier et al. expanded the rainbow connection concept of graphs to hypergraphs. They implemented it on a minimally connected hypergraph, an $ r $-uniform complete hypergraph, an $ r $-uniform cycle hypergraph, and an $ r $-uniform complete multipartite hypergraph. However, they did not determine the rainbow connection numbers of hypertrees. A hypergraph $ \mathcal{H} $ is called a hypertree if there exists a host tree $ T $ such that each edge of $ \mathcal{H} $ induces a subtree in $ T $. Therefore, in this article, we consider the rainbow connection numbers of some classes of $ s $-overlapping $ r $-uniform hypertrees with size $ t $. For $ r\geq 2 $, $ 1\leq s < r $, and $ t\geq 1 $, an $ s $-overlapping $ r $-uniform hypertree with size $ t $ is an $ r $-uniform connected hypertree, with $ s $ being the maximum cardinality of the vertex set obtained from the intersection of each pair of edges. We provide the best lower bound of the rainbow connection number of a connected hypergraph. Then, we determine the rainbow connection numbers of six classes of $ s $-overlapping $ r $-uniform hypertrees with size $ t $.

Keywords

• hypertree
• lower bound
• $ s $-overlapping $ r $-uniform hypergraph with size $ t $
• rainbow connection number