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.
DIMACS Home Page