A circular graph---counterexample to the Duchet kernel conjecture
\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.
- Graphes Noyau-Parfaits
- scientific article; zbMATH DE number 702896 (Why is no real title available?)
- scientific article; zbMATH DE number 3106184 (Why is no real title available?)
- On kernel-perfect critical digraphs
- Recent problems and results about kernels in directed graphs
- Solutions of irreflexive relations
- A note on Duchet's conjecture
- Vertex- and edge-minimal and locally minimal graphs
- A corrected version of the Duchet kernel conjecture
- The geometric kernel of integral circulant graphs
- Perfect graphs, kernels, and cores of cooperative games
- scientific article; zbMATH DE number 4152413 (Why is no real title available?)
- scientific article; zbMATH DE number 3989377 (Why is no real title available?)
- On CIS circulants
- The kernel in special directed circular graphs
- Circulant graphs with \(\det(-A(G))=-\deg(G)\): Codeterminants with \(K_n\)
- More on discrete convexity
- Some new families of KP-digraphs
This page was built for publication: A circular graph---counterexample to the Duchet kernel conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377838)
