Let G be a connected graph and f be a mapping from V (G) to S, where S is a set of k colors for some positive integer k. The color code of a vertex v of G with respect to f , denoted by codeG(v|f ), is the ordered (k + 1)- tuple (x0, x1, . . . , xk) where x0 is the color assigned to v and where xi is the number of vertices adjacent to v of color i for 1 ≤ i ≤ k, that is, xi = |{uv ∈ E(G) : f (u) = i}| for 1 ≤ i ≤ k. The mapping f is a recognizable coloring if codeG(u|f )̸ = codeG(v|f ) for every two distinct vertices u and v of G. The minimum number of colors needed for a recognizable coloring of G is the recognition number of G denoted by rn(G). Our goal in this article is to give the exact value of the recognition number of the corona product G ◦ H of two graphs G and H for the cases H = Kn and n ≥ |V (G)|, or G = Km and H = Kn with m > n. In addition, we obtain the exact value of the recognition number of the edge corona product G ⋄ H of G and H for the case that G is a non-trivial graph with minimum degree at least 2 and H = Kn where n ≥ |E(G)|. Moreover, an algorithm for computing the recognition number of graphs is presented. As an application of our algorithm, we compute the recognition number of some fullerene graphs.

Keywords