The Rainbow Connection Number of Triangular Snake Graphs
Resumo
Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention last years in Combinatorics. The rainbow connection number of a graph G is the least number of colors for a (not necessarily proper) edge coloring of G such that between any pair of vertices there is a path whose edge colors are all distinct. In this paper we determine the rainbow connection number of the triple triangular snake graphs.
Palavras-chave:
Connectivity (MSC05C40), Coloring of graphs and hypergraphs (MSC05C15), Paths and cycles (MSC05C38)
Referências
Ananth, P., Nasre, M., and Sarpatwar, K. K. (2011). Rainbow connectivity: Hardness and tractability. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), volume 13 of Leibniz International Proceedings in Informatics (LIPIcs), pages 241–251, Dagstuhl, Germany.
Chakraborty, S., Fischer, E., Matsliah, A., and Yuster, R. (2011). Hardness and algorithms for rainbow connectivity. Journal of Combinatorial Optimization, 21:330–347.
Chandran, L. S. and Rajendraprasad, D. (2012). Rainbow colouring of split and threshold graphs. In Int. Computing and Combinatorics Conference, pages 181–192. Springer.
Chartrand, G., Johns, G. L., McKeon, K. A., and Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 133(1):85–98.
Dudek, A., Frieze, A. M., and Tsourakakis, C. E. (2015). Rainbow connection of random regular graphs. SIAM Journal on Discrete Mathematics, 29(4):2255–2266.
Ehard, S., Glock, S., and Joos, F. (2019). A rainbow blow-up lemma for almost optimally bounded edge-colourings. arXiv preprint arXiv:1907.09950.
Gallian, J. A. (2014). A dynamic survey of graph labeling. The Electronic journal of combinatorics, 17:60–62.
Li, S. and Li, X. (2011). Note on the complexity of deciding the rainbow connectedness for bipartite graphs. arXiv preprint arXiv:1109.5534.
Li, X. and Sun, Y. (2010). Characterize graphs with rainbow connection number m − 2 and rainbow connection numbers of some graph operations. Preprint.
Li, X. and Sun, Y. (2012). Rainbow connections of graphs. Springer.
Lo, I. Y. (2012). Some bounds on the rainbow connection number of 3, 4 and 5-connected graphs. Preprint arXiv:1212.5934.
Montgomery, R., Pokrovskiy, A., and Sudakov, B. (2019). Decompositions into spanning rainbow structures. Proceedings of the London Mathematical Society, 119(4):899–959.
Rocha, A. and Almeida, S. M. (2017). Coloração arco-íris em grafos resultantes de produto cartesiano. In Proc. 37th Congress of the Brazilian Computer Society (CSBC’17/II ETC), pages 83–86, São Paulo.
Sandhya, S., Merly, E. E. R., and Deepa, S. (2016). Heronian mean labeling of triple triangular and triple quadrilateral snake graphs. International Journal of Applied Mathematical Sciences, 9:177–186.
Schiermeyer, I. (2009). Rainbow connection in graphs with minimum degree three. In International Workshop on Combinatorial Algorithms, pages 432–437. Springer.
Chakraborty, S., Fischer, E., Matsliah, A., and Yuster, R. (2011). Hardness and algorithms for rainbow connectivity. Journal of Combinatorial Optimization, 21:330–347.
Chandran, L. S. and Rajendraprasad, D. (2012). Rainbow colouring of split and threshold graphs. In Int. Computing and Combinatorics Conference, pages 181–192. Springer.
Chartrand, G., Johns, G. L., McKeon, K. A., and Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 133(1):85–98.
Dudek, A., Frieze, A. M., and Tsourakakis, C. E. (2015). Rainbow connection of random regular graphs. SIAM Journal on Discrete Mathematics, 29(4):2255–2266.
Ehard, S., Glock, S., and Joos, F. (2019). A rainbow blow-up lemma for almost optimally bounded edge-colourings. arXiv preprint arXiv:1907.09950.
Gallian, J. A. (2014). A dynamic survey of graph labeling. The Electronic journal of combinatorics, 17:60–62.
Li, S. and Li, X. (2011). Note on the complexity of deciding the rainbow connectedness for bipartite graphs. arXiv preprint arXiv:1109.5534.
Li, X. and Sun, Y. (2010). Characterize graphs with rainbow connection number m − 2 and rainbow connection numbers of some graph operations. Preprint.
Li, X. and Sun, Y. (2012). Rainbow connections of graphs. Springer.
Lo, I. Y. (2012). Some bounds on the rainbow connection number of 3, 4 and 5-connected graphs. Preprint arXiv:1212.5934.
Montgomery, R., Pokrovskiy, A., and Sudakov, B. (2019). Decompositions into spanning rainbow structures. Proceedings of the London Mathematical Society, 119(4):899–959.
Rocha, A. and Almeida, S. M. (2017). Coloração arco-íris em grafos resultantes de produto cartesiano. In Proc. 37th Congress of the Brazilian Computer Society (CSBC’17/II ETC), pages 83–86, São Paulo.
Sandhya, S., Merly, E. E. R., and Deepa, S. (2016). Heronian mean labeling of triple triangular and triple quadrilateral snake graphs. International Journal of Applied Mathematical Sciences, 9:177–186.
Schiermeyer, I. (2009). Rainbow connection in graphs with minimum degree three. In International Workshop on Combinatorial Algorithms, pages 432–437. Springer.
Publicado
30/06/2020
Como Citar
ROCHA, Aleffer; ALMEIDA, Sheila M.; ZATESKO, Leandro M..
The Rainbow Connection Number of Triangular Snake Graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 65-68.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11091.
