A circular graph---counterexample to the Duchet kernel conjecture (Q1377838): Difference between revisions

\textit{P. Duchet} and \textit{H. Meyniel} [Discrete Math. 33, 103-105 (1981; Zbl 0456.05032)] have conjectured, that if \(D\) is a digraph such that \(D-a\) has a kernel for every arc \(a\) of \(D\) then \(D\) is an odd circuit or has a kernel. The authors disprove this conjecture by applying the digraph \(G_{43}(1,7,8)\) whose vertex set is \(V=\{1,2,\dots,43\}\) and whose arcs are \(\{[i,i+j\bmod 43]:i\in V\) and \(j=1,7,8\}.\) \(G_{43}(1,7,8)\) is not a circuit, it has no kernel and the deletion of any arc of \(G_{43}(1,7,8)\) produces a digraph with a kernel.