The kernel-subdivision number of a digraph

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...

Full description

Saved in:
Bibliographic Details
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
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422