KERNELS IN DIRECTED-GRAPHS - A POISON GAME

被引：23

作者：

DUCHET, P

MEYNIEL, H

机构：

[1] CNRS,F-38042 GRENOBLE,FRANCE

[2] CNRS,F-75005 PARIS,FRANCE

来源：

DISCRETE MATHEMATICS | 1993年 / 115卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(93)90496-G

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider a two player game on a progressively and locally finite directed graph and we prove that the first player wins if and only if the graph has a local kernel. The result is sharp. From it, we derive a short proof of a general version of the Galeana-Sanchez & Neuman-Lara Theorem that give a sufficient condition for a digraph to be kernel-perfect.

引用

页码：273 / 276

页数：4