(Strong) Rainbow Connection Number of Line, Middle and Total Graph of Sunlet Graph

摘要

A path is called a rainbow path if no two edges of it are colored the same. An edge-colored graph is rainbow connected if every two distinct vertices are connected by a rainbow path. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors needed to make G rainbow connected. A rainbow u - v geodesic in a graph G is a rainbow u - v path of length d(u,v), where d(u,v) is the distance between u and v in G. A graph G is strongly rainbow connected if there exists a rainbow u - v geodesic for every pair of distinct vertices u and v in G. The strong rainbow connection number of G, denoted by src(G), is the smallest number of colors needed to make G strongly rainbow connected.The line, middle and total graphs are not only important graph classes, but also have extensive application in interconnect network design. In this paper, we determine exact values of rc(G) and src(G) where G are line and middle graphs of sunlet graph. In fact, all values of rc(G) and src(G) for these graphs determined before are incorrect.