论文标题
小精子猜想的结果
Results on the Small Quasi-Kernel Conjecture
论文作者
论文摘要
Digraph $ D $的A {\ em Quasi-Kernel}是独立集$ q \ subseteq v（d）$，因此，对于每个顶点$ v \ in V（d）\ backslash q $，都有一个或两个弧形的有向路径，从$ v $到pertex $ u \ in q $。 1974年，Chvátal和Lovász证明了每个Digraph都有准内核。 1976年，Erdős和Spekely猜想，每个无水槽的Digraph $ d =（v（d），a（d））$具有大小的准内核，最多$ | v（d）|/2 $。在本文中，我们给出了一种新方法，以表明该猜想是对无抗爪的挖掘物的概括。对于任何无水槽的单向拆分digraph $ d $ d $ n $的$ d $，当$ n \ geq 3 $时，我们表明$ d $具有最大尺寸的准核，最多最多$ \ frac {n+3} {2} {2} {2} {2} - \ sqrt {n} $，并且边界很锋利。
A {\em quasi-kernel} of a digraph $D$ is an independent set $Q\subseteq V(D)$ such that for every vertex $v\in V(D)\backslash Q$, there exists a directed path with one or two arcs from $v$ to a vertex $u\in Q$. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. In 1976, Erdős and Sźekely conjectured that every sink-free digraph $D=(V(D),A(D))$ has a quasi-kernel of size at most $|V(D)|/2$. In this paper, we give a new method to show that the conjecture holds for a generalization of anti-claw-free digraphs. For any sink-free one-way split digraph $D$ of order $n$, when $n\geq 3$, we show a stronger result that $D$ has a quasi-kernel of size at most $\frac{n+3}{2} - \sqrt{n}$, and the bound is sharp.
