On 15.08.2018 at 12:30 in S6, there is the following noon lecture:
Kernels, Grundy functions and circulant digraphs
Raúl González Silva
The concept of kernel was introduced by J. Von Neumann and it has been widely studied due to the numerous applications it has. The problem of deciding if a a digraph has kernel is NP-complete. A non-negative integer function g(x) is called a Grundy function on D if for every vertex x, g(x) is the smallest non-negative integer which does not belong to the ex-neighbourhood of x. If a digraph admits a Grundy function then it has a kernel, but kernel not necessarily implies Grundy function.
In this talk we will discuss the behaviour of Grundy function on the cartesian product of digraphs, and studied its behaviour on circulant digraphs: we want to characterize which circulant digraphs have kernel (problem proposed by Bang-Jensen). We will present some results that suggests that in this case could be equivalent to have kernel and to admit a Grundy function.
(This is a joint work with Hortensia Galeana-Sanchez.)
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019