论文标题
小准内核猜想的结果
A Result on the Small Quasi-Kernel Conjecture
论文作者
论文摘要
在这项工作中，任何有向图的$ d =（v（d），a（d））$被认为是有限的，没有自动浮动。有向图中的源是一个至少一个ingo弧的顶点。准内核$ q \ subseteq v（d）$是$ d $中的独立集，使得可以在$ v（d）$中的每个顶点在$ q $中的最多两个步骤中达到两个步骤。如果每个无源的有向图都具有$ | v（d）|/2 $，这是一个开放的问题，这是一个被称为小准内奶酪猜想（SQKC）的问题。本文的目的是在有向图的结构特性的假设下证明SQKC。这将SQKC与V（d）$中的顶点$ u \的存在以及当$ u $及其外部邻国从$ d $中删除时出现的新来源数量的存在。这项工作的结果具有技术性质，因此可以通过COQ证明辅助剂进行验证。
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.
