Kings and Kernels in Semicomplete Compositions

Let $k$ be an integer with $k\ge 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$;itis$\ell$-absorbentifforevery$x\in V(D)\setminus K$thereexists$y\in K$suchthat$d_D(x, y)\leq \ell$\mathrm{.}A$k$-kernelof$D$isa$k$-independentand$(k-1)$-absorbentsubsetof$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 {\sck$-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$isadigraphwith$t$vertices,and$H_1, \dots, H_t$arepairwisedisjointdigraphs\mathrm{.}Thecomposition$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\ge 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.