Acta Mechanica Slovaca 2018, 22(3):20-26 | DOI: 10.21496/ams.2018.022

On the Rainbow and Strong Rainbow Coloring of Comb Product Graphs

Dafik^1,2, I.H. Agustin^1,3, D.A.R. Wardanai^1,4, E.Y. Kurniawati^1,3, R. Alfarisi^1,5

¹ CGANT, University of Jember, Indonesia

² Mathematics Edu. Depart. University of Jember, Indonesia

³ Mathematics Depart. University of Jember, Indonesia

⁴ IKIP PGRI Jember, Indonesia

⁵ Department of Elementary School Teacher Education, University of Jember, Indonesia

Let G=(V,E) be a simple, nontrivial, finite, connected and undirected graph. Let c be a coloring c: E(G)g{1,2,…,k}, kdN. A path of the edges of a colored graph is said to be a rainbow path if no two edges on the path have the same color but the adjacent edges may be colored by the same colors. An edge colored graph G is rainbow connected if there exists a rainbow u-v path for every two vertices u and v of G. Furthermore, for any two vertices u and v of G, a rainbow u-v geodesic in G is a rainbow u-v path of length d(u,v), where d(u,v) is the distance between u and v. The graph G is strongly rainbow connected if there exists a rainbow u-v geodesic for any two vertices u and v in G. The rainbow and strong rainbow connection numbers of a graph G, denoted by rc(G) and src(G) respectively, are the minimum number of colors that are needed in order to make G rainbow and strongly rainbow connected, respectively. Some results have shown the lower and upper bound of rc(G) and src(G), but most of them are not sharp. Thus, finding an exact value of rc(G) and src(G) are significantly useful. In this paper, we study the exact values of rainbow and strong rainbow connection numbers of comb product graphs.

Keywords: rainbow connection; strong rainbow connection; comb product of graphs.

Published: September 15, 2018  Show citation