Rainbow and strong rainbow connection number for some families of graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-2020-04-0046Keywords:
Edge coloring, Rainbow coloring, Strong rainbow coloringAbstract
Let G be a nontrivial connected graph. Then G is called a rainbow connected graph if there exists a coloring c : E(G) → {1, 2, ..., k}, k ∈ 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 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 src(G) of G.
The exact rc and src of the rotationally symmetric graphs are determined.
Downloads
References
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
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
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
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
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
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
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
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
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
Z. Foruzanfar, F. Asif, Z. Zahid, S. Zafar, and M.R. Farahani, “ABC4 and GA5 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
Z. Foruzanfar, F. Asif, Z. Zahid, S. Zafar, and M. R. Farahani, “ABC4 and GA5 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
M. N. Husin, F. Asif, Z. Zahid, S. Zafar, and M. 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
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
R. Sohail, A. Rehman, M. Sh. R. Chowdhury, M. Imran, and M. 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
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
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
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
L. Yan, Y. Li, X. Zhang, M. Saqlain, S. Zafar, and M. 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
Downloads
Published
Issue
Section
License
Copyright (c) 2020 Yaqoub Ahmed Khan, Muhammad Naeem, Muhammad Kamran Siddiqui, Mohammad Reza Farahani
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.