• 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