DIMACS TR: 96-32
A Circular Graph -
Counterexample to the Duchet Kernel Conjecture
Authors: A. Apartsin, E. Ferapontova, V. Gurvich
ABSTRACT
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