On the family of r-regular graphs with Grundy number r+1

The Grundy number of a graph G, denoted by Gamma(G), is the largest k such that there exists a partition of V(G), into k independent sets V-1, . . . , V-k and every vertex of V-i is adjacent to at least one vertex in V-j, for every j < i. The objects which are studied in this article are families of r-regular graphs such that Gamma(G) = r + 1. Using the notion of independent module, a characterization of this family is given for r = 3. Moreover, we determine classes of graphs in this family, in particular, the class of r-regular graphs without induced C-4, for r <= 4. Furthermore, our propositions imply results on the partial Grundy number. (C) 2014 Elsevier B.V. All rights reserved.