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

Abstract

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,\dots ,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\le 4$. Furthermore, our propositions imply results on partial Grundy number.