Rainbow and strong rainbow connection number for some families of graphs

Authors

DOI:

https://doi.org/10.22199/issn.0717-6279-2020-04-0046

Keywords:

Edge coloring, Rainbow coloring, Strong rainbow coloring

Abstract

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.

Author Biographies

Yaqoub Ahmed Khan, Government College University.

Dept. of Mathematics.

Muhammad Naeem, Institute of Southern Punjab.

Dept. of Mathematics and Statistics.

Muhammad Kamran Siddiqui, Comsats University Islamabad.

Dept. of Mathematics.

Mohammad Reza Farahani, Iran University of Science and Technology.

Dept. of Applied Mathematics.

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

Published

2020-07-28

How to Cite

[1]
Y. A. Khan, M. Naeem, M. K. Siddiqui, and M. R. Farahani, “Rainbow and strong rainbow connection number for some families of graphs”, Proyecciones (Antofagasta, On line), vol. 39, no. 4, pp. 737-747, Jul. 2020.

Most read articles by the same author(s)