On the family of -regular graphs with Grundy number

详细信息    查看全文

• 作者：Nicolas Gastineau^a ; ^b ; ^{Nicolas.Gastineau@u-bourgogne.fr" class="auth_mail} ; Hamamache Kheddouci^b ; ^{hamamache.kheddouci@univ-lyon1.fr" class="auth_mail} ; Olivier Togni^a ; ^{Olivier.Togni@u-bourgogne.fr" class="auth_mail}
• 关键词：Grundy number ; False twin ; Partial Grundy number ; Regular graph
• 刊名：Discrete Mathematics
• 出版年：6 August 2014
• 年：2014
• 卷：328
• 期：Complete
• 页码：5-15
• 全文大小：733 K

文摘

The Grundy number of a graph G$G$, denoted by 螕(G)$螕\left(G\right)$, is the largest k$k$ such that there exists a partition of V(G)$V\left(G\right)$, into k$k$ independent sets V₁,…,V_k$V_1,\dots ,V_k$ and every vertex of V_i$V_i$ is adjacent to at least one vertex in V_j$V_j$, for every j<i$j<i$. The objects which are studied in this article are families of r$r$-regular graphs such that 螕(G)=r+1$螕\left(G\right)=r+1$. Using the notion of independent module, a characterization of this family is given for r=3$r=3$. Moreover, we determine classes of graphs in this family, in particular, the class of r$r$-regular graphs without induced C₄$C_4$, for r≤4$r\le 4$. Furthermore, our propositions imply results on the partial Grundy number.