Abstract
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 code G(v|f ), is the ordered (k + 1)tuple (x(0), x (1) , ... , x (k) ) where x 0 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 is an element of E ( G ) : f ( u ) = i }| for 1 < i < k . The mapping f is a recognizable coloring if codeG(u|f) not equal 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 degrees H of two graphs G and H for the cases H = K-n and n > | V ( G ) |, or G = K-m and H = K-n with m > n . In addition, we obtain the exact value of the recognition number of the edge corona product G lozenge 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.