DIMACS TR: 96-32

A Circular Graph - Counterexample to the Duchet Kernel Conjecture

Authors: A. Apartsin, E. Ferapontova, V. Gurvich


We construct a directed graph G such that a) G is strongly connected, b) G has the circular symmetry, c) G is not a directed odd cycle, d) G has no kernel but e) after removing any edge from G the obtained graph has a kernel.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-32.ps.gz
DIMACS Home Page