Grundy functions in the Cartesian Product

Abstract

Let D be a digraph, α = (α_v)_v∊V(D) a family where the α_v are mutually disjoint digraphs. The Cartesian product of α over D, denoted by σ(D,α) is defined as follows: (i) (ii)

A non-negative integer function g(x) is called a Grundy function on G if for every vertex x, g(x) is the smallest non-negative integer which does not belong to the set {g(y)|y ∊ Γ⁺(x)}. This concept was originated by Grundy in 1939, for digraphs without directed cycles. It was extended by C. Berge and Shützenberger in 1956. Also it was difused by C. Berge in 1956.

A set I ⊆ V(D) is independent if . A kernel N of D is an independent set of vertices such that for each z ∊ V(D) - N there exists a zN-arc. A digraph D is a kernel-perfect digraph whenever each one of its induced subdigraphs has a kernel.

The concepts of kernel of a digraph and Grundy function of a digraph are nearly related.

In this paper we prove sufficient and necessary conditions for the Cartesian Product σ(D, α) of a family of digraphs α = (α_v)_v∊V(D) over a digraph D to have a Grundy function in terms of the existence of Grundy function or kernel in D and in each α_v. Also it is shown a relationship between the size of the Grundy function obtained for σ(D, α) and the size of the Grundy functions of the factors α_v.

Keywords:

• Grundy function
• Cartesian product
• kernel
• kernel-perfect digraph

2010 Mathematics Subject Classification:

• 05C20