Department of
Applied
Mathematics

Kernels, Grundy functions and circulant digraphs

Raúl González Silva

Charles University

Abstract

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.)