Kings and Kernels in Semicomplete Compositions.

Let $T$ be a digraph with vertices $u_1, \dots, u_t$ ($t\ge 2$) and let $H_1, \dots, H_t$ be digraphs such that $H_i$ has vertices $u_{i,j_i},\ 1\le j_i\le n_i.$ Then the composition $Q=T[H_1, \dots, H_t]$ is a digraph with vertex set $\{u_{i,j_i}\mid 1\le i\le t, 1\le j_i\le n_i\}$ and arc set $$A(Q)=\cup^t_{i=1}A(H_i)\cup \{u_{ij_i}u_{pq_p}\mid u_iu_p\in A(T), 1\le j_i\le n_i, 1\le q_p\le n_p\}.$$ The composition $Q=T[H_1, \dots, H_t]$ is a semicomplete composition if $T$ is semicomplete, i.e. there is at least one arc between every pair of vertices. For the topic of kings, we first characterize digraph compositions with a $k$-king and digraph compositions all of whose vertices are $k$-kings, respectively. When $T$ is semicomplete, we discuss the existence of 3-kings, and the adjacency between a 3-king and a non-king in this class of digraphs. We also 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 of determining whether a strong semicomplete composition has a $k$-kernel is NP-complete when $k\in \{2,3\}$, and is polynomial time solvable when $k\geq 4$.