论文标题
国王和内核中的半完整成分
Kings and Kernels in Semicomplete Compositions
论文作者
论文摘要
让$ k $为$ k \ geq 2 $的整数。 Digraph $ d $中的$ k $ king是一个顶点，它可以通过$ k $的定向长度到达其他每个顶点，而非王者是一个顶点，这不是3个王者。子集$ k $是$ k $的独立于$ k $，如果每对顶点$ x，y \ in k $，我们都有$ d_d（x，y），d_d（y，x）\ geq k $;如果在v（d）\ setminus k $中的每一个$ x \中，则$ \ ell $ -absorbent中存在$ y \ in k $中的$ y \，以便$ d_d（x，y）\ leq \ ell $。 $ d $的$ k $ -kernel是$ k $独立的，$（k-1）$ - 吸收$ v（d）$的吸收子集。内核是2个内核。如果它是独立的，则$ k \ subseteq v（d）$是$ d $的准内核，对于v（d）\ setminus k $中的每个顶点$ x \，k $中存在$ y \ y y \ y y y \ y y \ y y \ y y \ y y \ y y \ y yd（x，x，y）\ leq 2 $。问题{\ sc $ k $ -kernel}正在确定给定的挖掘物是否具有$ K $ -KERNEL。 令$ q = t [h_1，\ dots，h_t] $为$ t $和$ h_i $的组成（$ 1 \ leq i \ leq i \ leq t，t \ ge 2 $），其中$ t $是$ t $ dertices的挖掘物，$ h_1，$ h_1，\ dots，\ dots，\ dots，h_t $ is ie Chanswise Disswise Difwise Difwise Difwise Difwise Difwise Difwise Digwise Digwise Digwise Digwise Digwise Digwise Digwise digwise digwiseD。构图$ q = t [h_1，\ dots，h_t] $是半完整的构图，如果$ t $是半完整的。在本文中，我们研究了半完整组成中的国王和内核。 对于国王的主题，我们用$ k $ king和Digraph构图表征了Digraph构图，其所有顶点分别为$ k $ kings。我们还讨论了3王的存在，并研究了强烈的半完整组成中的最小4夸夫。 对于内核的主题，我们首先研究了半完整组成中的一对脱节准内核。然后，我们推断出问题{\ sc $ k $ -kernel}限制在\ {2,3 \} $中的$ k \时，仅限于强的半完整构图是np-compterete，并且当$ k \ geq 4 $时是多项式溶解的。我们还证明，当$ k $由2或3排除时，问题{\ sc $ k $ -kernel}仅限于非strong np-np-complete。
Let $k$ be an integer with $k\geq 2$. A $k$-king in a digraph $D$ is a vertex which can reach every other vertex by a directed path of length at most $k$ and a non-king is a vertex which is not a 3-king. A subset $K$ is $k$-independent if for every pair of vertices $x,y \in K$, we have $d_D(x, y), d_D(y, x)\geq k$; it is $\ell$-absorbent if for every $x\in V(D)\setminus K$ there exists $y\in K$ such that $d_D(x, y)\leq \ell$. A $k$-kernel of $D$ is a $k$-independent and $(k-1)$-absorbent subset of $V(D)$. A kernel is a 2-kernel. A set $K\subseteq V(D)$ is a quasi-kernel of $D$ if it is independent, and for every vertex $x\in V(D)\setminus K$, there exists $y\in K$ such that $d_D(x, y)\leq 2$. The problem {\sc $k$-Kernel} is determining whether a given digraph has a $k$-kernel. Let $Q=T[H_1, \dots, H_t]$ be the composition of $T$ and $H_i$ ($1\leq i\leq t, t\ge 2$), where $T$ is a digraph with $t$ vertices, and $H_1, \dots, H_t$ are pairwise disjoint digraphs. The composition $Q=T[H_1, \dots, H_t]$ is a semicomplete composition if $T$ is semicomplete. In this paper, we study kings and kernels in semicomplete compositions. For the topic of kings, we characterize digraph compositions with a $k$-king and digraph compositions all of whose vertices are $k$-kings, respectively. We also discuss the existence of 3-kings, and study the minimum number of 4-kings in a strong semicomplete composition. For the topic of kernels, we first study the existence of a pair of disjoint quasi-kernels in semicomplete compositions. We then deduce that the problem {\sc $k$-Kernel} restricted to strong semicomplete compositions is NP-complete when $k\in \{2,3\}$, and is polynomial-time solvable when $k\geq 4$. We also prove that when $k$ is divisible by 2 or 3, the problem {\sc $k$-Kernel} restricted to non-strong semicomplete compositions is NP-complete.
