×

Rainbow and strong rainbow connection number for some families of graphs. (English) Zbl 1452.05065

Summary: Let \(G\) be a nontrivial connected graph. Then \(G\) is called a rainbow connected graph if there exists a coloring \(c : E(G) \rightarrow \{1, 2,\dots, k\}\), \(k\in N\), of the edges of \(G\), such that there is a \(u - v\) rainbow path between every two vertices of \(G\), where a path \(P\) in \(G\) is a rainbow path if no two edges of \(P\) are colored the same. The minimum \(k\) for which there exists such a \(k\)-edge coloring is the rainbow connection number \(\operatorname{rc}(G)\) of \(G\). If for every pair \(u\), \(v\) of distinct vertices, \(G\) contains a rainbow \(u - v\) geodesic, then \(G\) is called strong rainbow connected. The minimum \(k\) for which \(G\) is strong rainbow-connected is called the strong rainbow connection number \(\operatorname{src}(G)\) of \(G\).
The exact \(\operatorname{rc}\) and \(\operatorname{src}\) of the rotationally symmetric graphs are determined.

MSC:

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C40 Connectivity
Full Text: DOI

References:

[1] M. Alaeiyan and M. R. Farahani, “The 1-2-3-edge labeling and vertex colors”, International journal of applied mathematics and machine learning, vol. 4, no. 2, pp. 119-133, 2016, doi: 10.18642/ijamml_7100121608
[2] F. Asif, Z. Zahid, S. Zafar, M. R. Farahani, and W. Gao, “On topological properties of some convex polytopes by using line operator on their subdivisions”, Hacettepe journal of mathematics and statistics, vol. 49, no. 3, pp. 136-146, Jan. 2019, doi: 10.15672/HJMS.2019.671 · Zbl 1488.05076
[3] M. Baĉa, “On magic labellings of convex polytopes”, Annals of discrete mathematics, pp. 13-16, 1992, doi: 10.1016/S0167-5060(08)70599-5 · Zbl 0763.05089
[4] S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, “Hardness and algorithms for rainbow connectivity”, Leibniz international proceedings in informatics, pp. 243-254, 2009, doi: 10.4230/LIPIcs.STACS.2009.1811 · Zbl 1236.68080
[5] G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, “Rainbow connection in graphs”, Mathematica bohemica, vol. 133, no. 1, pp. 85-98, 2008. [On line]. Available: https://bit.ly/2AJRJwz · Zbl 1199.05106
[6] D. Estetikasari and S. Sy, “On the rainbow connection for some corona graphs”, Applied mathematical sciences, vol. 7, no. 100, pp. 4975-4980, 2013, doi: 10.12988/ams.2013.37410
[7] M. R. Farahani, “On The 1-2-3-edge weighting and vertex coloring of complete graph”, International journal on computational science & applications, vol. 3, no. 3, pp. 19-23, Jun. 2013, doi: 10.5121/ijcsa.2013.3302
[8] M. R. Farahani, “A new vertex-coloring edge-weighting of complete graphs”, Journal of applied mathematics & informatics, vol. 32, no. 1_2, pp. 1-6, Jan. 2014, doi: 10.14317/jami.2014.001 · Zbl 1285.05057
[9] M. R. Farahani and S. H. Hosseini ,“The 1-2-3-edge labeling and vertex coloring of complete graph Kn with a modified algorithm”, Algebras, Groups and Geometries, vol. 31, no. 2, pp. 183-199, 2014. [On line]. Available: https://bit.ly/3fth3pa · Zbl 1310.05090
[10] Z. Foruzanfar, F. Asif, Z. Zahid, S. Zafar, and M. R. Farahani, “ABC_4 and GA_5 indices of line graph of subdivisions of convex polytopes”, International journal of pure and applied mathematics, vol. 117, no. 4, pp. 645-653, 2017. [On line]. Available: https://bit.ly/3hC8sTi
[11] Z. Foruzanfar , F. Asif , Z. Zahid , S. Zafar , andM. R. Farahani , “ABC_4 and GA_5 indices of para-line graph of some convex polytope”, Statistics, optimization & information computing, vol. 7, no. 1, pp. 192-197, Jan. 2019, doi: 10.19139/soic.v7i1.346
[12] M. N. Husin, F. Asif , Z. Zahid , S. Zafar , andM. R. Farahani , “Fourth atom-bond connectivity index and fifth arithmetic-geometric index of convex polytopes by using line operator”, Advances and applications in discrete mathematics, vol. 19, no. 4, pp. 491-500, Oct. 2018, doi: 10.17654/DM019040491 · Zbl 1425.05046
[13] X. Li, Y. Shi, and Y. Sun, “Rainbow connections of graphs: a survey”, Graphs and combinatorics, vol. 29, no. 1, pp. 1-38, Oct. 2012, doi: 10.1007/s00373-012-1243-2 · Zbl 1258.05058
[14] R. Sohail, A. Rehman, M. Sh. R. Chowdhury, M. Imran, andM. R. Farahani , “Topological indices of some convex polytopes”, International journal of pure and applied mathematics , vol. 119, no. 3, pp. 451-460, 2018. [On line]. Available: https://bit.ly/2N69Waf
[15] S. Sy , R. Wijaya, and Surahmat, “Rainbow connection numbers of some graphs”, Applied mathematical sciences , vol. 8, no. 94, pp. 4693-4696, 2014, doi: 10.12988/ams.2014.46398
[16] B. Yang, M. Rashid, S. Ahmad, M. Nadeem, and M. Siddiqui, “Cycle super magic labeling of planar graphs”, International journal of applied mathematics, vol. 32, no. 6, pp. 945-957, 2019, doi: 10.12732/ijam.v32i6.4
[17] H. Yang, M. A. Rashid, S. Ahmad , M. K. Siddiqui, and M. F. Hanif, “Cycle super magic labeling of pumpkin, octagonal and hexagonal graphs”,Journal of discrete mathematical sciences and cryptography, vol. 22, no. 7, pp. 1165-1176, Dec. 2019, doi: 10.1080/09720529.2019.1698800 · Zbl 1495.05311
[18] L. Yan, Y. Li, X. Zhang, M. Saqlain, S. Zafar , andM. R. Farahani , “3-total edge product cordial labeling of some new classes of graphs”, Journal of information and optimization sciences, vol. 39, no. 3, pp. 705-724, Apr. 2018, doi: 10.1080/02522667.2017.1417727
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.