Title of article
A circular graph — counterexample to the Duchet kernel conjecture
Author/Authors
A. Apartsin، نويسنده , , E. Ferapontova، نويسنده , , V. Gurvich، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 1998
Pages
3
From page
229
To page
231
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 but the union of three such cycles with the same set of vertices and pairwise disjoint sets of edges, (d) G has no kernel but (e) after removing any edge from G the resulting graph has a kernel. Thus not only the directed odd cycles are connected edge-minimal kernel-less directed graphs.
Journal title
Discrete Mathematics
Serial Year
1998
Journal title
Discrete Mathematics
Record number
951326
Link To Document