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

Sitta Alief Farihati; A. N. M. Salman; Pritta Etriana Putri; Sitta Alief Farihati; A. N. M. Salman; Pritta Etriana Putri

doi:10.3934/math.2024916

AIMS Mathematics

2024, Volume 9, Issue 7: 18824-18840. doi: 10.3934/math.2024916

Previous Article Next Article

Research article

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

1.
Doctoral Program in Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jl. Ganesha 10, Bandung 40132, Indonesia
2.
Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jl. Ganesha 10, Bandung 40132, Indonesia
3.
Mathematics Study Program, Faculty of Science and Technology, Universitas Terbuka, Jl. Cabe Raya, Tangerang Selatan 15418, Indonesia

Received: 09 January 2024 Revised: 18 February 2024 Accepted: 27 February 2024 Published: 05 June 2024
MSC : 05C15, 05C65

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 $.
- hypertree,
- lower bound,
- $ s $-overlapping $ r $-uniform hypergraph with size $ t $,
- rainbow connection number
Citation: Sitta Alief Farihati, A. N. M. Salman, Pritta Etriana Putri. Rainbow connection numbers of some classes of $ s $-overlapping $ r $-uniform hypertrees with size $ t $[J]. AIMS Mathematics, 2024, 9(7): 18824-18840. doi: 10.3934/math.2024916

Related Papers:

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 $.

References

[1]	G. Chartrand, G. L. Johns, K. A. McKeon, P. Zhang, Rainbow connectivity of a graph, Networks, 54 (2009), 75–81. https://doi.org/10.1002/net.20296 doi: 10.1002/net.20296
[2]	G. Chartrand, G. L. Johns, K. A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem., 133 (2008), 85–98. https://doi.org/10.21136/MB.2008.133947 doi: 10.21136/MB.2008.133947
[3]	Dafik, I. H. Agustin, W. A. R. Wardanai, E. Y. Kurniawati, R. Alfarisi, On the rainbow and strong rainbow coloring of comb product graphs, Acta Mech. Slovaca, 22 (2018), 20–26. https://doi.org/10.21496/AMS.2018.022 doi: 10.21496/AMS.2018.022
[4]	D. Fitriani, A. N. M. Salman, Z. Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory Appl., 10 (2022), 461–473. https://doi.org/10.5614/ejgta.2022.10.2.9 doi: 10.5614/ejgta.2022.10.2.9
[5]	D. Estetikasari, S. Sy, On the rainbow connection for some corona graphs, Appl. Math. Sci., 7 (2013), 4975–4980. https://doi.org/10.12988/ams.2013.37410 doi: 10.12988/ams.2013.37410
[6]	N. Ramya, K. Rangarajan, R. Sattanathan, On rainbow coloring of some classes of graphs, Int. J. Comput. Appl., 46 (2012), 36–38.}
[7]	D. Fitriani, A. N. M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE Int. J. Graphs Comb., 13 (2016), 90–99. https://doi.org/10.1016/j.akcej.2016.03.004 doi: 10.1016/j.akcej.2016.03.004
[8]	T. Gologranc, G. Mekiš, I. Peterin, Rainbow connection and graph products, Graphs Combin., 30 (2014), 591-–607. https://doi.org/10.1007/s00373-013-1295-y doi: 10.1007/s00373-013-1295-y
[9]	X. L. Li, Y. F. Sun, Rainbow connection of graphs, New York: Springer, 2012. https://doi.org/10.1007/978-1-4614-3119-0
[10]	I. S. Kumala, A. N. M. Salman, The rainbow connection number of a flower ($C_m, K_n$) graph and a flower ($C_3, F_n$) graph, Procedia Comput. Sci., 74 (2015), 168–172. https://doi.org/10.1016/j.procs.2015.12.094 doi: 10.1016/j.procs.2015.12.094
[11]	S. Nabila, A. N. M. Salman, The rainbow connection number of origami graphs and pizza graphs, Procedia Comput. Sci., 74 (2015), 162–167. https://doi.org/10.1016/j.procs.2015.12.093 doi: 10.1016/j.procs.2015.12.093
[12]	D. Resty, A. N. M. Salman, Rainbow connection number of $n$-crossed prism graph and its corona product with a trivial graph, Procedia Comput. Sci., 74 (2015), 143–150. https://doi.org/10.1016/j.procs.2015.12.090 doi: 10.1016/j.procs.2015.12.090
[13]	M. A. Shulhany, A. N. M. Salman, The (strong) rainbow connection number of stellar graphs, AIP Conf. Proc., 1708 (2016), 060007. https://doi.org/10.1063/1.4941170 doi: 10.1063/1.4941170
[14]	D. N. S. Simamora, A. N. M. Salman, The rainbow (vertex) connection number of pencil graphs, Procedia Comput. Sci., 74 (2015), 138–142. https://doi.org/10.1016/j.procs.2015.12.089 doi: 10.1016/j.procs.2015.12.089
[15]	B. H. Susanti, A. N. M. Salman, R. Simanjuntak, The rainbow connection number of some subdivided roof graphs, AIP Conf. Proc., 1707 (2016), 020021. https://doi.org/10.1063/1.4940822 doi: 10.1063/1.4940822
[16]	Susilawati, A. N. M. Salman, Rainbow connection number of rocket graphs, AIP Conf. Proc., 1677 (2015), 030012. https://doi.org/10.1063/1.4930634 doi: 10.1063/1.4930634
[17]	X. L. Li, M. M. Liu, I. Schiermeyer, Rainbow connection number of dense graphs, Discuss. Math. Graph Theory, 33 (2013), 603–611. https://doi.org/10.7151/dmgt.1692 doi: 10.7151/dmgt.1692
[18]	A. Kemnitz, J. Przybylo, M. Wozniak, I. Schiermeyer, Rainbow connection in sparse graphs, Discuss. Math. Graph Theory, 33 (2013), 181–192. https://doi.org/10.7151/dmgt.1640 doi: 10.7151/dmgt.1640
[19]	A. Dudek, A. M. Frieze, C. E. Tsourakakis, Rainbow connection of random regular graphs, SIAM J. Discrete Math., 29 (2015), 2255–2266. https://doi.org/10.1137/140998433 doi: 10.1137/140998433
[20]	A. Frieze, C. E. Tsourakakis, Rainbow connection of sparse random graphs, Electron. J. Combin., 19 (2012), 1–19. https://doi.org/10.37236/2784 doi: 10.37236/2784
[21]	Y. L. Shang, A sharp threshold for rainbow connection of random bipartite graphs, Int. J. Appl. Math., 24 (2011), 149–153.
[22]	Y. Shang, A sharp threshold for rainbow connection in small-world networks, Miskolc Math. Notes, 13 (2012), 493–497. https://doi.org/10.18514/MMN.2012.347 doi: 10.18514/MMN.2012.347
[23]	R. P. Carpentier, H. Liu, M. Silva, T. Sousa, Rainbow connection for some families of hypergraphs, Discrete Math., 327 (2014), 40–50. https://doi.org/10.1016/j.disc.2014.03.013 doi: 10.1016/j.disc.2014.03.013
[24]	V. I. Voloshin, Introduction to graph and hypergraph theory, New York: Nova Science Publisher, 2009.
[25]	A. Bretto, Hypergraph theory, Cham: Springer, 2013. https://doi.org/10.1007/978-3-319-00080-0
[26]	C. Berge, Hypergraph: combinatorics of finite set, Amsterdam: Elsevier, 1984.
[27]	D. Král', J. Kratochvíl, A. Proskurowski, H. J. Voss, Coloring mixed hypertrees, Discrete Appl. Math., 154 (2006), 660–672. https://doi.org/10.1016/j.dam.2005.05.019 doi: 10.1016/j.dam.2005.05.019
[28]	M. J. Morgan, S. Mukwembi, H. C. Swart, On the eccentric connectivity index of a graph, Discrete Math., 311 (2011), 1229–1234. https://doi.org/10.1016/j.disc.2009.12.013 doi: 10.1016/j.disc.2009.12.013
[29]	C. D. Karamchedu, M. M. Klawe, On the Ramsey numbers of odd-linked double stars, Discrete Math., 345 (2022), 113001 https://doi.org/10.1016/j.disc.2022.113001 doi: 10.1016/j.disc.2022.113001
[30]	Amrullah, H. Assiyatun, E. T. Baskoro, S. Uttunggadewa, R. Simanjuntak, The partition dimension for a subdivision of homogeneous caterpillars, AKCE Int. J. Graphs Comb., 10 (2013), 317–325. https://doi.org/10.1080/09728600.2013.12088748 doi: 10.1080/09728600.2013.12088748
[31]	R. Boulet, The centipede is determined by its Laplacian spectrum, C. R. Math., 346 (2008), 711–716. https://doi.org/10.1016/j.crma.2008.05.014 doi: 10.1016/j.crma.2008.05.014
[32]	I. Schimeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory, 31 (2011), 387–395. https://doi.org/10.7151/dmgt.1553 doi: 10.7151/dmgt.1553
[33]	M. Budden, J. Hiller, A. Penland, Minimally connected $r$-uniform hypergraphs, Australas. J. Combin., 82 (2022), 1–20.
[34]	A. Dudek, A. Frieze, A. Rucinski, Rainbow Hamilton cycles in uniform hypergraphs, Electron. J. Combin., 19 (2012), 1–11. https://doi.org/10.37236/2055 doi: 10.37236/2055

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)