A Result on the Small Quasi-Kernel Conjecture
| Autor: | van Hulst, Allan |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Any directed graph $D=(V(D),A(D))$ in this work is assumed to be finite and without self-loops. A source in a directed graph is a vertex having at least one ingoing arc. A quasi-kernel $Q\subseteq V(D)$ is an independent set in $D$ such that every vertex in $V(D)$ can be reached in at most two steps from a vertex in $Q$. It is an open problem whether every source-free directed graph has a quasi-kernel of size at most $|V(D)|/2$, a problem known as the small quasi-kernel conjecture (SQKC). The aim of this paper is to prove the SQKC under the assumption of a structural property of directed graphs. This relates the SQKC to the existence of a vertex $u\in V(D)$ and a bound on the number of new sources emerging when $u$ and its out-neighborhood are removed from $D$. The results in this work are of technical nature and therefore additionally verified by means of the Coq proof-assistant. Comment: 9 pages, a link to the Coq code is mentioned in the paper, submitted to Electronic Journal of Combinatorics |
| Databáze: | arXiv |
| Externí odkaz: |
|