Research article

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

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

    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:

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



    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(602) PDF downloads(39) Cited by(0)

Article outline

Figures and Tables

Figures(6)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog