The kernel-subdivision number of a digraph

• Published in: arXiv.org 2023-12
• Main Authors: Hoekstra-Mendoza, Teresa I, Licona-Velázquez, Miguel E, Rojas-Monroy, Rocío
• Format: Article
• Language: English
• Subjects: Graph theory; Kernels
• ISSN: 2331-8422

It is well known that determining if a digraph has a kernel is an NP-complete problem. However, Topp proved that when subdividing every arc of a digraph we obtain a digraph with a kernel. In this paper we define the kernel subdivision number \(\kappa(D)\) of a digraph \(D\) as the minimum number of arcs, such that, when subdividing them, we obtain a digraph with a kernel. We give a general bound for \(\kappa(D)\) in terms of the number of directed cycles of odd length and compute \(\kappa(D)\) for a few families of digraphs. If the digraph is \(H\)-colored, we can analogously define the \(H\)-kernel subdivision number. In this paper we also improve a result for \(H\)-kernels given by Galeana et al. to subdividing every arc of a spanning subgraph with certain properties. Finally we prove that when the directed cycles of a digraph overlap little enough, we can obtain a good bound for the \(H\)-kernel subdivision number.