---
abstract: |
    In this survey we overview known results on digraph compositions which generalize several classes of digraphs, such as quasi-transitive digraphs. After an introductory section, the paper is divided into eight sections: connectivity, linkages, kings, kernels, paths, cycles, acyclic spanning subdigraphs, strong spanning subdigraphs. This survey also contains some conjectures and open problems for further study.

    \
    <span>**Keywords:**</span> digraph composition; semicomplete composition; connectivity; linkage; king; kernel; Hamiltonicity; path-cycle subdigraph; Path Partition Conjecture; pancyclicity; acyclic spanning subgraph; branching; strong spanning subdigraph.

    \
    <span>**AMS subject classification (2020)**</span>: 05C12, 05C20, 05C38, 05C40, 05C45, 05C69, 05C70, 05C75, 05C76, 05C85.
author:
- |
    Yuefang Sun\
    School of Mathematics and Statistics, Ningbo University,\
    Zhejiang 315211, P. R. China,\
    ybell@example.org
title: '**Compositions of Digraphs: A Survey**'
---

Introduction {#sec:intro}
============

In this section, we give the motivation for introducing the notion of digraph compositions by discussing the relationship between digraph compositions and several other digraph classes. Some notation and terminology are also given.

Digraph compositions and related digraph classes
------------------------------------------------

We refer the readers to @Bang-Jensen-Gutin [@Bondy] for graph-theoretical notation and terminology not given here. Throughout this survey, unless otherwise stated, paths and cycles are always assumed to be directed, and all digraphs considered in this paper have no parallel arcs or loops. We use $[n]$ to denote the set of all natural numbers from 1 to $n$.

A digraph $D$ is <span>*connected*</span> if $U(D)$ is connected, where $U(D)$ is the <span>*underlying graph*</span> of $D$. A digraph is <span>*acyclic*</span> if it has no directed cycle. A digraph $D$ is <span>*semicomplete*</span> if for every pair $x,y$ of distinct vertices of $D$, there is at least one arc between $x$ and $y.$ In particular, a <span>*tournament*</span> is a semicomplete digraph without a 2-cycle.

We often use the following operation called "composition" to construct "bigger" digraphs from "smaller" ones. 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.$ Let $n_0=\min\{n_i\mid 1\leq i\leq t\}$. Then the <span>*composition*</span> $Q=T[H_1, \dots, H_t]$ is a digraph with vertex set $$V(Q)=\{u_{i,j_i}\mid 1\le i\le t, 1\le j_i\le n_i\}$$ and arc set $$\left(\bigcup^t_{i=1}A(H_i) \right) \bigcup  \left( \bigcup_{u_iu_p\in A(T)} \{u_{ij_i}u_{pq_p} \mid 1\le j_i\le n_i, 1\le q_p\le n_p\} \right).$$ The composition $Q=T[H_1, \dots, H_t]$ is <span>*proper*</span> if $Q\neq T$, i.e. at least one $H_i$ is nontrivial, and is <span>*semicomplete*</span> if $T$ is semicomplete.

Digraph composition is related to another operation. Let $T$ be a digraph with vertex set $V(T)=\{u_i\mid i\in [t]\}$ and let $K$ be another digraph. By <span>*blowing up $u_i$ into $K$ in $T$*</span> we mean the operation that substitute the digraph $K$ for the vertex $u_i$ in $T$, that is, produces a new digraph $D=[\{u_1\}, \dots, \{u_{i-1}\}, K, \{u_{i+1}\}, \dots, \{u_t\}]$. Clearly, the digraph composition $Q=T[H_1, \dots, H_t]$ can be obtained from $T$ and $\{H_i\mid i\in [t]\}$ by blowing up $u_i$ into $H_i$ for each $i\in [t]$.

The notion of digraph composition can be used to define a class of decomposable digraphs. Note that if $Q=T[H_1, \dots, H_t]$, then $T, H_1, \dots, H_t$ are induced subdigraphs of $Q$ and we say that $Q$ is <span>*decomposable*</span> (into $T, H_1, \dots, H_t$). Let $\Phi$ be a class of digraphs. A digraph $Q$ is <span>*$\Phi$-decomposable*</span> if $Q\in \Phi$ or $Q=T[H_1, \dots, H_t]$ for some $T\in \Phi$ with $t=|T|\geq 2$ and some choice of digraphs $H_1, \dots, H_t$, and this decomposition is called a <span>*$\Phi$-decomposition*</span>. In particular, we say that a digraph $Q$ is <span>*totally $\Phi$-decomposable*</span> if either $Q\in \Phi$ or $Q=T[H_1, \dots, H_t]$ with $T\in \Phi$ and $H_i$ totally $\Phi$-decomposable for $i\in [t]$. The <span>*total $\Phi$-decomposition*</span> of $Q$ is inductively defined as the sequence: $$\left\{
   \begin{array}{ll}
     Q, &\mbox {if $Q\in \Phi$;}\\
     T, L_1, \dots, L_t,~$where$~L_i~$is~the~total$~\Phi-$decomposition~of~$H_i, &\mbox {Otherwise.}
   \end{array}
   \right.$$ The <span>*first flyer*</span> of the total $\Phi$-decomposition of $Q=T[H_1, \dots, H_t]$, namely, $T, H_1, \dots, H_t$ is called the <span>*$\Phi$-decomposition*</span> of $D$. There are several important digraph classes which are subclasses of digraph compositions. Interestingly, some of them are also subclasses of totally $\Phi$-decomposable digraphs. If $Q=T[H_1, \dots, H_t]$ and none of the digraphs $H_1, \dots, H_t$ has an arc, then $Q$ is an <span>*extension*</span> of $T$. For any set $\Phi$ of digraphs, $\Phi^{ext}$ denotes the (infinite) set of all extensions of digraphs in $\Phi$, which are called <span>*extended $\Phi$-digraphs*</span>. For example, if $\Phi$ is the set of all semicomplete digraphs, then $\Phi^{ext}$ denotes the set of all extended semicomplete digraphs. Clearly, extended semicomplete digraphs are totally $\Phi_1$-decomposable, where $\Phi_1$ is the set of all semicomplete digraphs and acyclic digraphs.

A digraph $D$ is <span>*quasi-transitive*</span>, if for any triple $x,y,z$ of distinct vertices of $D$, if $xy$ and $yz$ are arcs of $D$ then either $xz$ or $zx$ or both are arcs of $D.$ The following theorem by Bang-Jensen and Huang gives a complete characterization of quasi-transitive digraphs which shows that quasi-transitive digraphs are totally $\Phi_1$-decomposable. The decomposition below is called the <span>*canonical decomposition*</span> of a quasi-transitive digraph.

\[intro01\]@Bang-Jensen-Huang1 Let $D$ be a quasi-transitive digraph. Then the following assertions hold:

(a)

:   If $D$ is not strong, then there exists a transitive oriented graph $T$ with vertices $\{u_i\mid i\in [t]\}$ and strong quasi-transitive digraphs $H_1, H_2, \dots, H_t$ such that $D = T[H_1, H_2, \dots, H_t]$, where $H_i$ is substituted for $u_i$, $i\in [t]$.

(b)

:   If $D$ is strong, then there exists a strong semicomplete digraph $S$ with vertices $\{v_j\mid j\in [s]\}$ and quasi-transitive digraphs $Q_1, Q_2, \dots, Q_s$ such that $Q_j$ is either a vertex or is non-strong and $D = S[Q_1, Q_2, \dots, Q_s]$, where $Q_j$ is substituted for $v_j$, $j\in [s]$.

A digraph $D$ is <span>*locally semicomplete*</span> if $N^-(x)$ and $N^+(x)$ induce semicomplete digraphs for every vertex $x$ of $D$. A <span>*locally tournament digraph*</span> or <span>*local tournament*</span> is a locally semicomplete digraph without a 2-cycle. A digraph on $n$ vertices is <span>*round*</span> if we can label its vertices $u_1, \dots, u_n$ such that for each $i$, we have $N^+(u_i)=\{u_j\mid i+1\leq j\leq i+d^+(u_i)\}$ and $N^-(u_i)=\{u_j\mid i-d^-(u_i)\leq j\leq i-1\}$ (all subscripts are taken modulo $n$). Note that every round digraph is locally semicomplete. A locally semicomplete digraph $D$ is <span>*round decomposable*</span> if there exists a round local tournament $R$ on $r\geq 2$ vertices such that $D=R[S_1, \dots, S_r]$, where each $S_i$ is a strong semicomplete digraph. We call $R[S_1, \dots, S_r]$ a <span>*round decomposition*</span> of $D$. Clearly, round decomposable locally semicomplete digraphs are totally $\Phi_2$-decomposable, where $\Phi_2$ is the set of all semicomplete digraphs and round digraphs. By an <span>*evil locally semicomplete digraph*</span> we mean a locally semicomplete digraph that is not semicomplete and not round decomposable. It is worth mentioning that Bang-Jensen, Guo, Gutin and Volkmann used the notion of round decomposition to give a full classification of locally semicomplete digraphs @Bang-Jensen-Guo-Gutin-Volkmann.

\[intro03\]@Bang-Jensen-Guo-Gutin-Volkmann Let $D$ be a locally semicomplete digraph. Then exactly one of the following possibilities holds. Furthermore, given a locally semicomplete digraph $D$, we can decide in polynomial time which of the possibilities holds for $D$:

(a)

:   $D$ is round decomposable with a unique round decomposition $D=R[S_1,\\ \dots, S_r]$, where $R$ is a round local tournament on $r\geq 2$ vertices and each $S_i$ is a strong semicomplete digraph for $i\in [r]$.

(b)

:   $D$ is evil.

(c)

:   $D$ is a semicomplete digraph that is not round decomposable.

The <span>*lexicographic product*</span> $G\circ H$ of two digraphs $G$ and $H$ is a digraph with vertex set $V(G\circ H)=V(G)\times V(H)=\{(x,
x')\colon\, x\in V(G), x'\in V(H)\}$ and arc set $A(G\circ
H)=\{(x,x')(y,y')\colon\, xy\in A(G),~or~x=y~and~x'y'\in
A(H)\}$ (e.g., @Hammack). By definition, we directly have $G\circ H=G[H,\dots, H]$.

Recall that digraph compositions generalize several families of digraphs, including extended semicomplete digraphs, quasi-transitive digraphs, round decomposable locally semicomplete digraphs and lexicographic product digraphs. In particular, semicomplete compositions generalize strong quasi-transitive digraphs. To see that strong compositions form a significant generalization of strong quasi-transitive digraphs, observe that the Hamiltonian cycle problem is polynomial-time solvable for quasi-transitive digraphs @Gutin4, but NP-complete for strong semicomplete compositions (see, e.g., @Bang-Jensen-Gutin-Yeo). While digraph composition has been used since 1990s to study locally semicomplete digraphs, quasi-transitive digraphs and their generalizations, see, e.g., @Bang-Jensen-Guo-Gutin-Volkmann [@Bang-Jensen2; @Bang-Jensen-Huang1; @GSHC], the study of digraph compositions in their own right was initiated only recently by Sun, Gutin and Ai in @Sun-Gutin-Ai. In this paper we survey known results on digraph compositions. The mainbody of this survey is divided into eight sections: connectivity, linkage, kings, kernels, paths, cycles, acyclic spanning subdigraphs, strong spanning subdigraphs. Some conjectures and open problems are also posed for further study in this survey.

Further notation and terminology
--------------------------------

Let $D$ be a digraph. If there is an arc from a vertex $x$ to a vertex $y$ in $D$, then we say that $x$ <span>*dominates*</span> $y$ and denote it by $x\rightarrow y$. If there is no arc from $x$ to $y$ we shall use the notation $x\not\rightarrow y$. If $A$ and $B$ are two subdigraphs of $D$ and every vertex of $A$ dominates each vertex of $B$, then we say that $A$ <span>*dominates*</span> $B$ and denote it by $A\rightarrow B$. We shall use $A\Rightarrow B$ to denote that $A$ dominates $B$ and there is no arcs from $B$ to $A$. A digraph $D$ is <span>*triangular*</span> with a partition $\{V_0, V_1, V_2\}$, if $V(D)$ can be partitioned into three disjoint sets $V_0, V_1, V_2$ with $V_0\Rightarrow V_1\Rightarrow V_2\Rightarrow V_0$. We use $N^-(x)$ (resp. $N^+(x)$) to denote the set of all in-neighbours (resp. out-neighbours) of a vertex $x$ in a digraph $D$.

A <span>*$k$-king*</span> in a digraph $D$ is a vertex which can reach every other vertex by a directed path of length at most $k$. A $k$-king $x$ is <span>*strict*</span> if there exists a vertex $y$ such that $d_D(x, y)=k$, where $d_D(x, y)$ denotes the length of a shortest path from $x$ to $y$ in $D$. A 2-king is called a <span>*king*</span>, and a <span>*non-king*</span> is a vertex which is not a 3-king. We call a vertex $x$ in a digraph a <span>*sink*</span> (resp. <span>*source*</span>) if $d^+(x)=0$ (resp. $d^-(x)=0$).

A set $S$ of vertices in a digraph $D$ is <span>*independent*</span> if $D[S]$ has no arcs. A subset $K$ is <span>*$k$-independent*</span> if for every pair of vertices $x,y \in K$, we have $d(x, y), d(y, x)\geq k$; it is called <span>*$\ell$-absorbent*</span> if for every $x\in V(D)\setminus K$ there exists $y\in K$ such that $d(x, y)\leq \ell$. A set $K\subseteq V(D)$ is call a <span>*kernel*</span> of $D$ if it is an independent set such that every vertex in $V(D)\setminus K$ dominates some vertex in $K$. A set $Q\subseteq V(D)$ is call a <span>*quasi-kernel*</span> of $D$ if it is an independent set such that, for every vertex $x\in V(D)\setminus Q$, there exist $y\in V(D)\setminus Q$ and $z\in Q$ such that either $xz\in A(D)$ or $xy, yz\in A(D)$. A <span>*$k$-kernel*</span> of $D$ is a $k$-independent and $(k-1)$-absorbent subset of $V(D)$. Clearly, a 2-kernel is exactly a kernel. The problem <span>$k$-Kernel</span> is determining whether a given digraph has a $k$-kernel.

The <span>*complementary graph*</span> of a graph $G$ is denoted by $\overline{G}$. A digraph $D$ is said to be <span>*strong*</span>, if for every pair of vertices $x$ and $y$, there is a path from $x$ to $y$ in $D$ and vice versa. A <span>*strong component*</span> of a digraph $D$ is a maximal induced subdigraph of $D$ which is strong. An <span>*initial*</span> (resp. <span>*terminal*</span>) <span>*strong component*</span> is one which has no arcs entering (resp. leaving) it. We call a set $S\subseteq V(D)$ a <span>*separator*</span> of $D$ if $D-S$ is not strong. A separator $S$ is <span>*minimal*</span> if no proper subset of $S$ is a separator. A digraph is <span>*$k$-strong-connected*</span> if every separator has at least $k$ vertices. An <span>*out-tree*</span> (resp. <span>*in-tree*</span>) <span>*rooted at a vertex $r$*</span> is an orientation of a tree such that the in-degree (resp. out-degree) of every vertex but $r$ equals one. An <span>*out-branching*</span> $B^+_r$ (resp. <span>*in-branching*</span> $B^-_r$) in a digraph $D$ is a spanning subdigraph of $D$ which is out-tree (resp. in-tree).

A digraph $D$ is <span>*pancyclic*</span> if $D$ contains a cycle of length $k$ for each $3\leq k\leq n$, and is <span>*vertex-pancyclic*</span> if every vertex of $D$ is contained in a cycle of length $k$ for each $3\leq k\leq n$. A cycle (path) of a digraph $D$ is <span>*Hamiltonian*</span> if it contains all the vertices of $D$. A digraph is <span>*Hamiltonian*</span> if it has a Hamiltonian cycle. A <span>*$k$-path-cycle subdigraph*</span> $\mathcal{F}$ of a digraph $D$ is a collection of $k$ paths $P_1, \dots, P_k$ and $t$ cycles $C_1, \dots, C_t$ such that all of $P_1, \dots, P_k, C_1, \dots, C_t$ are pairwise disjoint (possibly, $k=0$ or $t=0$). We will denote $\mathcal{F}$ by $\mathcal{F}=P_1\cup \dots \cup P_k\cup C_1\cup \dots \cup C_t$. Furthermore, a <span>*$k$-path-cycle factor*</span> is a spanning $k$-path-cycle subdigraph. If $t=0$, $\mathcal{F}$ is a <span>*$k$-path subdigraph*</span> and it is a <span>*$k$-path factor*</span> (or just a <span>*path factor*</span>) if it is spanning. If $k=0$, we say that $\mathcal{F}$ is a <span>*$t$-cycle subdigraph*</span> (or just a <span>*cycle subdigraph*</span>) and it is a <span>*$t$-cycle factor*</span> (or just a <span>*cycle factor*</span>) if it is spanning. The <span>*path covering number*</span> of a digraph $D$, denoted $pc(D)$, is the smallest $k$ for which $D$ has a <span>*$k$-path factor*</span>. Note that a Hamiltonian path is a 1-path factor. For every digraph $D$ with at least one cycle and every non-negative integer $j$, we define $\eta_j(D)=\min \{i\mid D$ has a $i$-path-$j$-cycle factor$\}$.

Let $\mathcal{F}=C_1\cup \dots \cup C_t$ be a $t$-cycle factor of a digraph $D$. We say $\mathcal{F}$ is <span>*reducible*</span> if there exists a $t'$-cycle factor $\mathcal{F'}=C_1\cup \dots \cup C_{t'}$ of $D$ such that each of the following holds:\
$(a)$ $t'<t$;\
$(b)$ for every $i\in [t]$ there is a $j\in [t']$ such that $V(C_i)\subseteq V(C'_j)$.\
Such a $\mathcal{F'}$ is called a <span>*reduction*</span> of $\mathcal{F}$. If no reduction of $\mathcal{F}$ exists, then $\mathcal{F}$ is said to be <span>*irreducible*</span>. Clearly, every minimum cycle factor is irreducible.

A digraph is <span>*locally in-semicomplete*</span> (resp. <span>*locally out-semicomplete*</span>) if $N^-(x)$ (resp. $N^+(x)$) induces a semicomplete digraph for every vertex $x$ of $D$. A digraph is <span>*semicomplete multipartite*</span> if it is obtained from a complete multipartite graph by replacing every edge by an arc or a pair of opposite arcs. A <span>*multipartite tournament*</span> is a semicomplete multipartite digraph without a 2-cycle. A digraph is called <span>*symmetric*</span> if for every arc $xy$ there is an opposite arc $yx$. Let $\overline{K}_p$ stand for the digraph of order $p$ with no arcs, and $\overrightarrow{C}_k$ and $\overrightarrow{P}_k$ denote the cycle and path with $k$ vertices, respectively.

Connectivity {#sec:connectivity}
============

Let $\mathcal{T}_1$ be the set of all semicomplete digraphs $T$ satisfying the following: there exists a vertex $u$ such that $uv, vu\in A(T)$ for any $v\in V(T)\setminus \{u\}$. The following result concerns the structure of a minimal separator in a strong semicomplete composition $Q=T[H_1, \dots, H_t]$ when $T\not \in \mathcal{T}_1$.

\[connectivity1\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition with $T\not \in \mathcal{T}_1$. Then every minimal separator $S$ of $Q$ induces in $\overline{U(Q)}$ a subgraph which consists of some connected components of $\overline{U(Q)}$. Moreover, each vertex $s\in S$ is adjacent to every vertex of $Q-S$.

Note that the above result may not hold when $T\in \mathcal{T}_1$. Consider the following example @Sun2: let $T$ be a semicomplete digraph such that for each $1\leq j\leq t$, $u_1u_j, u_ju_1\in A(T)$ and $H_i$ is a cycle of length four: $u_{i,1}, u_{i,2}, u_{i,3}, u_{i,4}, u_{i,1}$. Observe that $S=\{u_{1,1}\}\cup (\bigcup_{i=2}^t{V(H_i)})$ is a minimal separator of $Q$, and $\overline{U(Q)}$ consists of $2t$ components (each component is an edge). Clearly, the edge $\{u_{1,1}, u_{1,3}\}$ is one such component, however, $u_{1,1}\in S$ and $u_{1,3}\not\in S$.

In the same paper, Sun continued to study the connectivity of semicomplete compositions as follows.

\[connectivity2\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a $k$-strong-connected semicomplete composition with $T\not \in \mathcal{T}_1$. If $V(H_i)$ induces a connected component of $\overline{U(Q)}$ for some $i\in [t]$, then deleting all arcs in $H_i$ results in a $k$-strong-connected semicomplete composition.

Note that Theorem \[connectivity2\] may not hold if $T\in \mathcal{T}_1$. Consider the following example @Sun2: let $T$ be a 2-cycle, and $H_i$ be a $2k$-cycle for each $1\leq i\leq 2$, where $k\geq 3$. Clearly, $T\in \mathcal{T}_1$. Observe that each $V(H_i)$ induces a connected component in $\overline{U(Q)}$ for $1\leq i\leq 2$. Indeed, each such component consists of two vertex-disjoint cliques of size $k$ and edges between them. Let $Q'$ be the subdigraph of $Q$ by deleting all arcs in $H_1$. It can be checked that $V(H_2)$ is a separator of size $k$ in $Q'$. However, there is no separator of size $k$ in $Q'$. Hence, $Q$ is $(k+1)$-strong-connected, but $Q'$ is not $(k+1)$-strong-connected.

The following result on strong quasi-transitive digraphs was given by Bang-Jensen and Huang.

\[connectivity01\]@Bang-Jensen-Huang1 Every strong quasi-transitive digraph $D$ with at least four vertices has two distinct vertices $v_1, v_2$ such that $D-v_i$ is strong for $i\in [2].$

Sun extended Theorem \[connectivity01\] to strong semicomplete compositions.

\[connectivity3\]@Sun2 Every strong semicomplete composition $Q=T[H_1, \dots, H_t]$ with at least four vertices has two distinct vertices $v_1, v_2$ such that $Q-v_i$ is strong for $i\in [2].$

Linkages {#sec:linkage}
========

Let $s_1, s_2, \dots, s_k, t_1, t_2, \dots, t_k$ be distinct vertices of a digraph $D$. A <span>*$k$-linkage*</span> from $(s_1, s_2, \dots, s_k)$ to $(t_1, t_2, \dots, t_k)$ in $D$ is a set of vertex-disjoint paths $P_1,\dots ,P_k$ such that $P_i$ is an $(x_i, y_i)$-path in $D$. A digraph $D$ is <span>*$k$-linked*</span> if it contains a $k$-linkage from $(s_1, s_2, \dots, s_k)$ to $(t_1, t_2, \dots, t_k)$ for every choice of distinct vertices $s_1, s_2, \dots, s_k, t_1, t_2, \dots, t_k$.

\[link1\]@Bang-Jensen-ADM1989 Every 5-strong semicomplete digraph is 2-linked and this is best possible even for tournaments.

\[link2\]@Bang-Jensen-DM1999 Let $Q=\overrightarrow{C}_2[H_1, H_2]$ where $H_i$ is an arbitrary digraph on $n_i$ vertices for $i\in [2]$. If $Q$ is 4-strong, then $Q$ is 2-linked.

\[link3\]@Bang-Jensen-DM1999 Let $k\geq 4$ be an integer and let $T$ be a digraph on at least two vertices with the property that every $k$-strong digraph of the form $T[S_1, S_2, \dots, S_t]$ is 2-linked, where $S_i$ is a semicomplete digraph on $n_i$ vertices for each $i\in [t]$. Let $Q=T[H_1, H_2, \dots, H_t]$, where $H_i$ is an arbitrary digraph on $n_i$ vertices. If $Q$ is $k$-strong, then $Q$ is 2-linked.

Bang-Jensen @Bang-Jensen-DM1999 deduced that every 5-strong quasi-transitive digraph is 2-linked. Sun extended this result to 5-strong semicomplete compositions by Theorem \[link1\], Lemmas \[link2\] and \[link3\].

\[link4\]@Sun3 Every 5-strong semicomplete composition is 2-linked.

Kings {#sec:king}
=====

The study of kings in digraphs began with Landau @Landau and the term king was introduced by Maurer @Maurer. The concept of $k$-king was first introduced in @Bang-Jensen-Huang2 for the purpose of studying quasi-transitive digraphs. After spending some years dormant, this subject has received a lot of attention lately. Many of the nice existing results for kings in quasi-transitive digraphs admit natural generalizations to $k$-quasi-transitive digraphs @Bang-Jensen-Gutin [@GSHC]. By Theorem \[intro01\], digraph compositions generalize quasi-transitive digraphs, it is natural to study $k$-kings of this class of digraphs.

$T$ is arbitrary
----------------

For any integer $k\geq 2$, Sun characterized all digraph compositions with a $k$-king and digraph compositions all of whose vertices are $k$-kings.

\[king1\]@Sun Let $k\geq 2$ be an integer, and $Q=T[H_1, \dots, H_t]$ be a digraph composition. Then the following assertions hold:

(a)

:   $Q$ has a $k$-king if and only if $T$ has a $k$-king $u_{i}$ for some $i\in [t]$ and at least one of the following possibilities holds: $(i)$ $H_{i}$ has a $k$-king; $(ii)$ $|V(H_{i})|\geq 2$ and $u_{i}$ belongs to a cycle of $T$ with length at most $k$.

(b)

:   All vertices of $Q$ are $k$-kings if and only if for each $i\in [t]$, $u_{i}$ is a $k$-king of $T$ and at least one of the following possibilities holds: $(i)$ all vertices of $H_{i}$ are $k$-kings of $H_i$; $(ii)$ $|V(H_{i})|\geq 2$ and $u_{i}$ belongs to a cycle of $T$ with length at most $k$.

$T$ is semicomplete
-------------------

The following result can be found in literature, see e.g. Theorem 2.2.9 of @Bang-Jensen-Havet.

\[king05\] Every strong semicomplete digraph is vertex-pancyclic.

\[king06\]@Landau Every tournament has a king. More precisely, every vertex with maximum out-degree is a king.

Bang-Jensen and Huang obtained the following result on the existence of 3-kings in a quasi-transitive digraph.

\[Bang-Huangking\]@Bang-Jensen-Huang2 Let $D$ be a quasi-transitive digraph with a 3-king. If $D$ has no source, then $D$ has at least two 3-kings.

Sun gave a similar result to Theorem \[Bang-Huangking\] for semicomplete compositions.

\[king3\]@Sun Let $Q=T[H_1, \dots, H_t]$ be a semicomplete composition with a 3-king. If $T$ has no source, then $Q$ has at least two 3-kings. In particular, every strong semicomplete composition $Q=T[H_1, \dots, H_t]$ has a 3-king, and a vertex $v\in H_i$ is a 3-king of $Q$ if and only if $u_i$ is a 3-king of $T$.

<span>**Remark A**</span>: According to the argument for Theorem \[king3\], we actually can divide $H_1, \dots, H_t$ in a strong semicomplete composition $Q=T[H_1, \dots, H_t]$ into those for which all $v\in H_i$ are 3-kings (in this case, $u_i$ is a 3-king of $T$) and those for which no $v\in H_i$ is a 3-king.

Recall that in Theorem \[Bang-Huangking\], Bang-Jensen and Huang @Bang-Jensen-Huang2 proved that a quasi-transitive digraph $D$ with a 3-king contains at least two 3-kings provided that it has no source. It is also worth noting that we cannot replace the condition "If $T$ has no source" in Theorem \[king3\] by "If $Q$ has no source", according to the following example @Sun: let $Q=T[H_1, \dots, H_t]$ be a semicomplete composition such that $u_i$ dominates (but is not dominated by) $u_j$ for any $1\leq i< j\leq t$, and $H_1$ is a digraph with vertex set $\{u_{1, j}\mid 1\leq j\leq 6\}$ and arc set $\{u_{1,j}u_{1,j+1}, u_{1,j+1}u_{1,j} \mid 1\leq j\leq 6\}$. It can be checked that $Q$ has no source but $u_{1,4}$ is the unique 3-king of $Q$.

The following result concerns the adjacency between 3-kings and non-kings.

\[king4\]@Sun Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition. Then there is an arc between every 3-king and every non-king; moreover, for every non-king $u$, there exists a 3-king $v$ such that $d_Q(u, v)>3$ and $v$ dominates $u$.

Bang-Jensen and Huang @Bang-Jensen-Huang2 proved that Theorem \[king4\] holds for a quasi-transitive digraph with a 3-king, which means that the result may hold even for a non-strong quasi-transitive digraph (as long as it has a 3-king). However, for a non-strong semicomplete composition $Q$ with a 3-king, Theorem \[king4\] may not hold. We just use the example after Theorem \[king3\]: $Q$ is not strong and $u_{1,4}$ is the unique 3-king of $Q$; furthermore, there is no arc between $u_{1,4}$ and $u_{1,1}$, and of course $u_{1,4}$ does not dominate $u_{1,1}$.

For a semicomplete composition $Q$, if there exists a semicomplete composition $Q'$ which contains $Q$ as an induced subdigraph such that the set of all 3-kings of $Q'$ is precisely $V(Q)$, then we say $Q$ can be <span>*established*</span>. Similar problems for tournaments and quasi-transitive digraphs have been studied in @Bang-Jensen-Huang2 [@Huang-Li; @Reid]. Sun gave a sufficient condition under which a semicomplete composition can be established. It suffices to study strong semicomplete compositions with a non-king, since the case that all vertices are 3-kings is trivial.

\[king5\]@Sun Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition. If $T$ has a strict 3-king and every 2-king of $T$ is dominated by some strict 3-king of $T$, then $Q$ can be established.

For strong semicomplete multipartite digraphs, Gutin and Yeo obtained a result on the number of 4-kings.

\[king01\]@Gutin-Yeo Every strong semicomplete multipartite digraph with at least six vertices has at least five 4-kings.

The following result on semicomplete bipartite digraphs was first stated by Wang and Zhang @Wang-Zhang, and was mentioned in @GSHC (see Theorem 8.6.7).

\[king02\] Let $D$ be a semicomplete bipartite digraph with a unique initial strong component. If there is no 3-king in $D$, then there are at least eight 4-kings in $D$.

For multipartite tournaments, Koh and Tan got the following result.

\[king03\]@Koh-Tan [@Koh-Tan2] If a multipartite tournament has a unique initial strong component and no 3-king, then it has at least eight 4-kings.

It is worth noting that many results for strong multipartite tournaments also hold for strong semicomplete multipartite digraphs, due to the following result by Volkmann.

\[king04\]@Volkmann Every strong semicomplete $c$-partite digraph with $c \geq 3$ contains a spanning strong oriented subdigraph.

By Theorems \[king01\], \[king02\], \[king03\] and \[king04\], Sun obtained the following result which deals with the minimum number of 4-kings in a strong semicomplete composition.

\[king6\]@Sun Every strong semicomplete composition $Q=T[H_1, \dots, H_t]$ with at least six vertices has at least five 4-kings. Furthermore, if $Q$ has no 3-king, then it has at least eight 4-kings.

There is a generalization of the concept of kings. A <span>*monochromatic king*</span> in an arc-coloured digraph is a vertex $x$ such that for every vertex $y$, there is a monochromatic $x-y$ path. Sands, Sauer and Woodrow @Sands-Sauer-Woodrow proved that every 2-coloured tournament $T$ has a monochromatic king. Shen @Shen showed that if no subtournament of order 3 in a given arc-coloured tournament get three different colours on its arcs, then $T$ has a monochromatic king. It is natural to consider the following question of digraph compositions.

\[op-king\]Give a sufficient condition under which a given arc-coloured digraph composition contains a monochromatic king.

Kernels {#sec:kernel}
=======

The concept of a kernel was introduced by von Neumann and Morgenstern while studying cooperative games @Neumann-Morgenstern. After that, kernels have been studied in many areas, such as list coloring, game theory and perfect graphs @Boros-Gurvich, mathematical logic @Bezem-Grabmayer-Walicki and complexity theory @Walicki-Dyrkolbotn.

Chvátal and Lovász obtained the following result on the existence of a quasi-kernel in digraphs.

\[thmkernel02\]@Chvatal-Lovasz Every digraph contains a quasi-kernel.

Gutin et al. @Gutin-Koh-Tay-Yeo characterized digraphs with exactly one or two quasi-kernels. In particular, if a digraph has precisely two quasi-kernels then these two quasi-kernels are actually disjoint. This raises the question of which digraphs contains a pair of disjoint quasi-kernels. Heard and Huang @Heard-Huang gave sufficient conditions to guarantee the existence of a pair of disjoint quasi-kernels in several classes of digraphs, including semicomplete digraphs, semicomplete multipartite digraphs, quasi-transitive digraphs and locally semicomplete digraphs.

@Heard-Huang\[thmkernel01\] Every semicomplete digraph $D$ with no sink contains two vertices $x, y$ such that $\{x\}$ and $\{y\}$ are both quasi-kernels of $D$.

By Theorems \[thmkernel02\] and \[thmkernel01\], Sun obtained the following result on the existence of disjoint quasi-kernels in semicomplete compositions.

\[thmkernel2\]@Sun Let $Q=T[H_1, \dots, H_t]$ be a semicomplete composition such that $T$ has no sink. Then $Q$ contains a pair of disjoint quasi-kernels. In particular, every strong semicomplete composition contains a pair of disjoint quasi-kernels.

The following result provides a necessary condition for a semicomplete composition to have a $k$-kernel when $k\geq 3$.

\[lemkernel1\]@Sun Let $Q=T[H_1, \dots, H_t]$ be a semicomplete composition. If $Q$ contains a $k$-kernel with $k\geq 3$, then there is a vertex $v\in V(Q)$ such that $\{v\}$ is a $(k-1)$-absorbent set of $Q-(V(H_i)\setminus \{v\})$ where $v\in V(H_i)$ for some $i\in [t]$.

Furthermore, when $k\geq 4$, we can characterize strong semicomplete compositions with a $k$-kernel.

\[lemkernel4\]@Sun Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition and $k\geq 4$. Then $Q$ has a $k$-kernel if and only if there is a vertex $v\in V(Q)$ such that $\{v\}$ is a $(k-1)$-absorbent set of $Q-(V(H_i)\setminus \{v\})$ where $v\in V(H_i)$ for some $i\in [t]$.

\[lemkernel2\]@Sun Let $Q=T[H_1, \dots, H_t]$ be a digraph composition and $v\in V(H_i)$ for some $i\in [t]$. Then $\{v\}$ is a $k$-absorbent set of $Q-(V(H_i)\setminus \{v\})$ if and only if $\{u_i\}$ is a $k$-absorbent set of $T$.

The problem <span>$2$-Kernel</span> (also called <span>Kernel</span>) is NP-Complete @Chvatal, even restricted to planar digraphs with $\Delta\leq 3, \Delta^+, \Delta^-\leq 2$ @Fraenkel, or digraphs with 3-colourable underlying graph @Hell-Hernandez-Cruz. However, when restricted to quasi-transitive digraphs, the above problem can be solved in polynomial time @Hell-Hernandez-Cruz. For the <span>$3$-Kernel</span> problem, Hell and Hernández-Cruz @Hell-Hernandez-Cruz proved that it is NP-complete even when restricted to cyclically 3-partite digraphs of circumference 6, but can be solved in polynomial time restricted to semicomplete multipartite digraphs or 3-quasi-transitive digraphs. By Lemmas \[lemkernel4\] and \[lemkernel2\], Sun proved the complexity of <span>$k$-Kernel</span> restricted to strong semicomplete compositions for any integer $k\geq 2$.

\[thmkernel3\]@Sun Let $k\geq 2$ be an integer. The problem <span>$k$-Kernel</span> restricted to strong semicomplete compositions is NP-complete when $k\in \{2,3\}$, and is polynomial time solvable when $k\geq 4$.

It is worth noting that there is a generalization of the concept of $k$-kernels. A digraph $D$ is called <span>*$m$-coloured*</span> if the arcs of $D$ are coloured with $m$ colours. A path from $x$ to $y$ in $D$ is $\ell$-coloured if its arcs uses exactly $\ell$ colours. A subset $S\subseteq V(D)$ with $|S|\neq 0$ is called a <span>*$k$-coloured independent set*</span> if for every pair $x, y\in S$, there is no $\ell$-coloured path from $x$ to $y$; and is called a <span>*$k$-coloured absorbent set*</span> if for every vertex $x\in V(D)\setminus S$ there exists $y\in S$ such that there is a $\ell$-coloured path from $x$ to $y$, where $\ell\leq k$. A set $K \setminus V(D)$ is called a <span>*$k$-coloured kernel*</span> if $K$ is a $k$-coloured independent set and a $k$-coloured absorbent set. This notion was introduced in @Galeana-Llano-Montellano-Ballesteros, and was studied in other literature, such as @Galeana-Llano-Ballesteros. It is natural to ask the following question.

\[opkernel2\] What is the complexity of determining whether a given arc-coloured semicomplete composition has a $k$-coloured kernel, where $k\geq 2$?

Paths {#sec:path}
=====

Hamiltonian paths
-----------------

Gutin proved the following result on Hamiltonian paths and cycles of extended semicomplete digraphs.

\[path01\]@Bang-Jensen-Gutin-Huang An extended semicomplete digraph has a Hamiltonian path (resp. cycle) if and only if it has a 1-path-cycle factor (resp. it is strong and has a cycle factor).

By the above theorem, Sun characterized those semicomplete compositions which have a Hamiltonian path.

\[path1\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a semicomplete composition. Then $Q$ has a Hamiltonian path if and only if it has a 1-path-cycle factor $\mathcal{F}=P\cup C_1\cup \dots \cup C_k~(k\geq 0)$ such that neither $V(P)$ nor $V(C_i)$ is completely contained in a connected component of $\overline{U(Q)}$.

Path subdigraphs
----------------

The following structural characterization of longest cycles in extended semicomplete digraphs was extensively used.

\[path02\]@Bang-Jensen-Huang-Yeo Let $Q=T[\overline{K}_{n_1}, \dots, \overline{K}_{n_t}]$ be a strong extended semicomplete digraph. For $i\in [t]$, let $m_i$ denote the maximum number of vertices from $\overline{K}_{n_i}$ which can be covered by a cycle subdigraph of $Q$. Then every longest cycle of $Q$ contains precisely $m_i$ vertices from $\overline{K}_{n_i}$ for each $i\in [t]$.

Bang-Jensen et al. proved a similar result for $k$-path subdigraphs in an extended semicomplete digraph.

\[path03\]@Bang-Jensen-Nielsen-Yeo Let $Q=T[\overline{K}_{n_1}, \dots, \overline{K}_{n_t}]$ be an extended semicomplete digraph and let $\ell_{i,k}$ denote the maximum number of vertices of $\overline{K}_{n_i}$ that can be covered by a $k$-path subdigraph in $Q$. Then every maximum $k$-path subdigraph in $Q$ covers exactly $\ell_{i,k}$ vertices of $\overline{K}_{n_i}$ for each $i\in [t]$.

By Theorem \[path03\], Bang-Jensen et al. got the following result on a strong semicomplete composition when each $H_i$ is either a single vertex or a non-strong quasi-transitive digraph.

\[path04\]@Bang-Jensen-Nielsen-Yeo Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition with order $n$, where each $H_i$ is either a single vertex or a non-strong quasi-transitive digraph. For every $k\in [n]$ and $i\in [t]$, there exists an integer $n_{i,k}$ such that every maximum $k$-path subdigraph $\mathcal{F}$ of $Q$ satisfies $|V(H_i) \cap V(\mathcal{F})|=n_{i,k}$ and no $k$-path subdigraph of $Q$ contains more than $n_{i,k}$ vertices of $H_i$.

Sun extended Theorem \[path04\] to all strong semicomplete compositions.

\[path2\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition with order $n$. For every $k\in [n]$ and $i\in [t]$, there exists an integer $n_{i,k}$ such that every maximum $k$-path subdigraph $\mathcal{F}$ of $Q$ satisfies $|V(H_i) \cap V(\mathcal{F})|=n_{i,k}$ and no $k$-path subdigraph of $Q$ contains more than $n_{i,k}$ vertices of $H_i$.

The argument for Theorem \[path2\] also means that Theorem \[path03\] holds for a strong semicomplete composition. Note that the number $\ell_{i, k}$ in Theorem \[path3\] is exactly $n_{i, k}$ of Theorem \[path2\].

\[path3\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition and let $\ell_{i,k}$ denote the maximum number of vertices of $H_i$ that can be covered by a $k$-path subdigraph in $Q$. Then every maximum $k$-path subdigraph in $Q$ covers exactly $\ell_{i,k}$ vertices of $H_i$ for each $i\in [t]$.

The following nice property holds for several classes of digraphs (such as semicomplete multipartite digraphs @Gutin3): For a digraph $D$ with a 1-path-cycle subdigraph $\mathcal{F}=P_1\cup C_1\cup \dots \cup C_t$, there exists a path $P$ of $D$ such that $V(P)=V(P_1)\cup(\bigcup_{j=1}^t{V(C_j)})$. However, this property does not hold for a general semicomplete composition, according to the following example: Let $Q=T[H_1, H_2]$ be a strong semicomplete composition such that $H_1$ is a path and $H_2$ consists of a set of disjoint cycles $C_1, \dots, C_t$, where $|V(H_1)|\leq t-2$. Clearly, $\mathcal{F}=H_1\cup C_1\cup \dots \cup C_t$ is a 1-path-cycle subdigraph but there is no path $P$ such that $V(P)=V(H_1)\cup(\bigcup_{j=1}^t{V(C_j)})$. Hence, one may try to study the following question.

\[op4\]Give a sufficient condition under which the above property holds for a semicomplete composition.

Path partition conjecture
-------------------------

Let $\ell(D)$ denote the order of a longest directed path in a digraph $D$. The Gallai-Roy-Vitaver Theorem @Gallai [@Roy; @Vitaver] states that the chromatic number of the underlying graph of a digraph $D$ is at most $\ell(D)$. Laborde et al. @Laborde posed a conjecture which extends this theorem in a natural way: Every digraph $D$ contains an independent set $X$ such that $\ell(D-X)< \ell(D)$. This conjecture is a particular instance of what is called the <span>*Path Partition Conjecture*</span> which states the following:

\[conj01\]@Laborde For every digraph $D$ and any pair of positive integers $\ell_1$ and $\ell_2$ with $\ell(D)=\ell_1+\ell_2$, there exists a partition of $D$ into two subdigraphs $D_1$ and $D_2$, such that $\ell(D_i) \leq \ell_i$ for $i \in [2]$.

The following more stronger version of Conjecture \[conj01\] is stated in @Bondy1.

\[conj02\]@Bondy1 For every digraph $D$ and any pair of positive integers $\ell_1$ and $\ell_2$ with $\ell(D)=\ell_1+\ell_2$, there exists a partition of $D$ into two subdigraphs $D_1$ and $D_2$, such that $\ell(D_i)= \ell_i$ for $i \in [2]$.

In @Bang-Jensen-Nielsen-Yeo, Conjecture \[conj01\] is proved for several generalizations of tournaments, including quasi-transitive, extended semicomplete and locally in-semicomplete digraphs. Arroyo and Galeana-Sánchez @Arroyo continued the research of Path Partition Conjecture for some generalizations of tournaments. The following conjecture is equivalent to Conjecture \[conj01\].

\[conj03\]@Arroyo For every digraph $D$ and a positive integer $q< \ell(D)$, there exists a partition $(A, B)$ of $V(D)$ such that $\ell(D[A])\leq q$ and $\ell(D[B])\leq \ell(D)-q$.

Arroyo and Galeana-Sánchez proved the following results on Conjecture \[conj03\] for digraph compositions.

\[path4\]@Arroyo Let $Q=T[H_1, \dots, H_t]$ be a digraph composition and $q$ be a positive integer less than $\ell(D)$, where $T$ is an acyclic digraph. Suppose that for each $H_i$ and for each positive integer $q_i$ with $q_i<\ell(H_i)$, there exists a partition $(A_i, B_i)$ of $V(H_i)$ such that $\ell(H_i[A_i])\leq q_i$ and $\ell(H_i[B_i])\leq \ell(H_i)-q_i$. Then there exists a partition $(A, B)$ of $V(Q)$ such that $\ell(Q[A])\leq q$ and $\ell(Q[B])\leq \ell(Q)-q$.

\[path5\]@Arroyo Let $H_1=\overline{K}_{n_1}, H_t=\overline{K}_{n_t}$, and $H_i~(2\leq i\leq t-1)$ be digraphs satisfying that for each positive integer $q_i$ with $q_i<\ell(H_i)$, there exists a partition $(A_i, B_i)$ of $V(H_i)$ with the property that $\ell(H_i[A_i])\leq q_i$ and $\ell(H_i[B_i])\leq \ell(H_i)-q_i$. Consider the composition $Q=\overrightarrow{C}_t[H_1, \dots, H_t]$ and a positive integer $q< \ell(D)$. Then there exists a partition $(A, B)$ of $V(Q)$ such that $\ell(Q[A])\leq q$ and $\ell(Q[B])\leq \ell(Q)-q$.

Cycles {#sec:cycle}
======

Hamiltonian cycles
------------------

With a similar argument to that of Theorem \[path1\], Sun provided the first characterization of Hamiltonian semicomplete compositions which extends a characterization of Hamiltonian quasi-transitive digraphs given by Bang-Jensen and Huang @Bang-Jensen-Huang1.

\[cycle1\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a semicomplete composition. Then $Q$ has a Hamiltonian cycle if and only if it is strong and contains a cycle factor $\mathcal{F}=C_1\cup \dots \cup C_k$, such that no $V(C_i)$ is completely contained in a connected component of $\overline{U(Q)}$.

Gutin obtained the following result on long cycles in strong extended semicomplete digraphs.

\[Gutin-longcycle\]@Gutin2 Let $D$ be a strong extended semicomplete digraph and let $\mathcal{F}$ be a cycle subdigraph of $D$. Then $D$ has a cycle $C$ which contains all vertices of $\mathcal{F}$. In particular, if $V(\mathcal{F})$ is maximum, then $V(C)=V(\mathcal{F})$ and $C$ is a longest cycle of $D$.

By Theorem \[Gutin-longcycle\], Sun extended a characterization of Hamiltonian quasi-transitive digraphs which is given by Gutin @Gutin4 to strong semicomplete compositions, and provide the second characterization of Hamiltonian semicomplete compositions.

\[cycle3\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition. Then $Q$ has a Hamiltonian cycle if and only if the extended semicomplete digraph $Q'=T[\overline{K}_{n_1}, \dots, \overline{K}_{n_t}]$ has a cycle subdigraph which covers at least $pc(H_i)$ vertices of $\overline{K}_{n_i}$ for every $i \in [t]$.

Pancyclicity
------------

Gutin characterized pancyclic and vertex-pancyclic extended semicomplete digraphs.

\[cycle01\]@Gutin Let $D$ be a Hamiltonian extended semicomplete digraph on $n\geq 4$ vertices such that $\overline{U(D)}$ has $k\geq 3$ connected components. Then the following assertions hold:

(a)

:   $D$ is pancyclic if and only if $D$ is not triangular with a partition $\{V_0, V_1, V_2\}$, two of which induce independent sets, such that either $|V_0|=|V_1|=|V_2|$ or no $D[V_i]$ $(i= 0, 1, 2)$ contains a path of length 2.

(b)

:   $D$ is vertex-pancyclic if and only if it is pancyclic and either $k>3$ or $k = 3$ and $D$ contains two cycles $C, C'$ of length 2 such that $C \cup C'$ has vertices in each of the three connected components of $\overline{U(D)}$.

The next two lemmas by Bang-Jensen and Huang @Bang-Jensen-Huang1 concern cycles in triangular digraphs.

\[cycle02\]@Bang-Jensen-Huang1 Suppose that $D$ is a Hamiltonian triangular digraph with a partition $\{V_0, V_1, V_2\}$. If $D[V_1]$ contains an arc $xy$ and $D[V_2]$ contains an arc $uv$, then every vertex of $V_0\cup \{x, y, u, v\}$ is on cycles of lengths $3, 4, \dots, |V(D)|$.

\[cycle03\]@Bang-Jensen-Huang1 Suppose that $D$ is a triangular digraph with a partition $\{V_0, V_1, V_2\}$ and has a Hamiltonian cycle $C$. If $D[V_0]$ contains an arc of $C$ and a path $P$ of length 2, then every vertex of $V_1\cup V_2\cup V(P)$ is on cycles of lengths $3, 4, \dots, |V(D)|$.

By Theorem \[cycle01\], Lemmas \[cycle02\] and \[cycle03\], Sun got the following result on the pancyclicity of semicomplete compositions, and this extends a similar result for quasi-transitive digraphs by Bang-Jensen and Huang @Bang-Jensen-Huang1.

\[cycle2\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a Hamiltonian semicomplete composition on $n\geq 4$ vertices. Then $Q$ is pancyclic if and only if it is not triangular with a partition $\{V_0, V_1, V_2\}$, two of which induce independent sets, such that either $|V_0|=|V_1|=|V_2|$, or no $Q[V_i]~(i=0, 1, 2)$ contains a path of length 2.

Theorem \[cycle2\] completely characterizes pancyclic Hamiltonian semicomplete compositions, but we still have no idea for the characterization of vertex-pancyclic Hamiltonian semicomplete compositions.

\[op2\]Characterize Hamiltonian semicomplete compositions which are vertex-pancyclic.

Recall that Theorem \[Gutin-longcycle\] states that a strong extended semicomplete digraph $D$ has a cycle $C$ which contains all vertices of $\mathcal{F}$, where $\mathcal{F}$ is a cycle subdigraph of $D$. In particular, if $V(\mathcal{F})$ is maximum, then $V(C)=V(\mathcal{F})$ and $C$ is a longest cycle of $D$. Gutin also got the following result on strong semicomplete bipartite digraphs.

\[Gutin-1\]@Gutin2 Let $D$ be a strong semicomplete bipartite digraph. The length of a longest cycle in $D$ is equal to the number of vertices in a cycle subdigraph of $D$ of maximum order.

However, it seems that Theorems \[Gutin-longcycle\] and \[Gutin-1\] do not hold for strong semicomplete compositions, according to the following example @Sun2: Let $Q=T[H_1, H_2]$ be a strong semicomplete composition such that $|V(H_2)|=|V(H_1)|+2$, $H_1$ has no arcs, $H_2$ contains a 2-cycle and has no other arcs. Since $Q$ is strong and $t=2$, $T$ is a 2-cycle. Observe that the order of a maximum cycle subdigraph of $Q$ is $|V(Q)|$, but the length of the longest cycle is $|V(Q)|-1$. Therefore, it is interesting to study the following question.

\[op1\]Let $Q=T[H_1, \dots, H_t]$ be a strong semicomplete composition. Give a sufficient condition under which the length of a longest cycle in $Q$ is equal to the number of vertices in a cycle subdigraph of $Q$ of maximum order (or, $Q$ has a cycle $C$ which contains all vertices of a given cycle subdigraph $\mathcal{F}$ of $Q$).

Cycle factors
-------------

For a digraph composition $Q=T[H_1, H_2, \dots, H_t]$, those cycles of a cycle factor $\mathcal{F}$ that are contained in a $H_i$ are called <span>*small*</span> cycles and all other cycles of $\mathcal{F}$ are called <span>*large*</span> cycles. Using Theorem \[path02\], Sun proved the following result:

\[cyclefactor1\]@Sun3 Let $\mathcal{F}$ be an irreducible cycle factor in a strong semicomplete composition $Q=T[H_1, H_2, \dots, H_t]$. Then $\mathcal{F}$ has exactly one large cycle. In particular, every minimum cycle factor in a strong semicomplete composition contains exactly one large cycle.

Let $\mathcal{C}$ be the set of cycle subdigraphs of $T[\overline{K}_{n_1}, \dots, \overline{K}_{n_t}]$ which is the corresponding extended semicomplete digraph of a strong semicomplete composition $Q=T[H_1, H_2, \dots, H_t]$. For each $i\in [t]$, let $$m_i(Q)=\max_{\mathcal{S}\in \mathcal{C}}\{|V(\mathcal{S})\cap V(\overline{K}_{n_i})|\}.$$ By Theorem \[path02\], every longest cycle in $T[\overline{K}_{n_1}, \dots, \overline{K}_{n_t}]$ contains exactly $m_i(Q)$ vertices of $V(\overline{K}_{n_i})$.

\[cyclefactor2\]@Sun3 If $Q=T[H_1, H_2, \dots, H_t]$ is a strong semicomplete composition containing a cycle factor then $Q$ has a minimum cycle factor in which the (unique) large cycle $C$ intersects $H_i$ in exactly $m_i(Q)$ paths for each $i\in [t]$. That is, by contracting each maximal subpath of $C$ which lies inside $H_i$ (for every $i\in [t]$), we obtain a longest cycle of $T[\overline{K}_{n_1}, \dots, \overline{K}_{n_t}]$.

A <span>*canonical*</span> minimum cycle factor is one for which the unique large cycle intersects each $H_i$ in exactly $m_i(Q)$ paths. By Lemma \[cyclefactor2\], every strong semicomplete composition with a cycle factor has a canonical minimum cycle factor.

Let $I(Q)=\{i\mid m_i(Q)<pc(H_i)\}$ and note that for every $i$, $H_i$ has the same number $c_i$ of small cycles with respect to every canonical minimum cycle factor. Observe that the number $c_i=0$ when $i\not\in I(Q)$. Furthermore, it can be checked that $c_i=\min\{j\mid \eta_j(H_i)=m_i(Q)\}$. Therefore, we have the following characterization of the number, $k_{\min}(Q)$, of cycles in a minimum cycle factor of a strong semicomplete composition.

\[cyclefactor3\] Let $Q=T[H_1, H_2, \dots, H_t]$ be a strong semicomplete composition with a cycle factor. Then $$k_{\min}(Q)=1+\sum_{i\in I(Q)}{\min\{j\mid \eta_j(H_i)=m_i(Q)\}}.$$

Note that Theorem \[cyclefactor3\] extends a similar result for strong quasi-transitive digraphs (see Theorem 21 of @Bang-Jensen-Nielsen): Let $D$ be a strong quasi-transitive digraph with a cycle factor which has a canonical decomposition $D=T[H_1, H_2, \dots, H_t]$. Then $k_{\min}(D)=1+\sum_{i\in I(D)}{\min\{j\mid \eta_j(H_i)=m_i(D)\}}$. Bang-Jensen and Nielsen studied the problem of determining the complexity of computing $k_{\min}(D)$ and finding a minimum cycle factor of a quasi-transitive digraph $D$, and deduced that when $k_{\min}(D)$ is small, in particular when $k_{\min}(D)=\{1,2,3\}$, the above problem is polynomially solvable. However, when we consider the same problem on strong semicomplete compositions, it becomes NP-complete even when $k_{\min}(D)=1$, as in this case the problem is exactly the Hamiltonian cycle problem which was proved to be NP-complete for strong semicomplete compositions @Bang-Jensen-Gutin-Yeo.

Acyclic spanning subdigraphs {#sec:ass}
============================

The existence of prescribed acyclic spanning subdigraphs
--------------------------------------------------------

It is well known that a tournament $T$ contains an $x-y$ Hamiltonian path if and only if there is an acyclic spanning subdigraph $R$ (not necessarily induced) such that for each vertex $z$ of $T$, $R$ contains an $x-z$ path and a $z-y$ path @Thomassen2. Bang-Jensen and Huang @Bang-Jensen-Huang1 proved that if a quasi-transitive digraph has both in- and out-branchings then it always contains such an acyclic spanning subdigraph. For semicomplete compositions, Sun gave the following sufficient condition to guarantee the existence of this type of subdigraph.

\[ass1\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a semicomplete composition. Then it contains an acyclic spanning subdigraph $R$ with a source $x$ and a sink $y$ such that for each vertex $z$ of $Q$, $R$ contains an $x-z$ path and a $z-y$ path, if one of the following assertions holds:

(a)

:   $Q$ is non-strong and has both in- and out-branchings.

(b)

:   $Q$ is strong with $|V(H_i)|\geq 2$ for each $i\in [t]$.

The author used the Hamiltonicity (Theorem \[king05\]) of a strong semicomplete digraph in the proof for the case that $Q$ is strong with $|V(H_i)|\geq 2$ for each $i$ in Theorem \[ass1\]. In fact, the proof also means that the following more general result holds.

\[ass2\]@Sun2 Let $Q=T[H_1, \dots, H_t]$ be a digraph composition. If $T$ is Hamiltonian and $|V(H_i)|\geq 2$ for each $i\in [t]$, then $Q$ contains an acyclic spanning subdigraph $R$ with a source $x$ and a sink $y$ such that for each vertex $z$ of $Q$, $R$ contains an $x-z$ path and a $z-y$ path.

In Theorem \[ass2\], the existence of prescribed acyclic spanning subdigraphs in strong semicomplete compositions with $|V(H_i)|\geq 2$ for each $i\in [t]$ were studied. It is natural to extend this to all strong semicomplete compositions. However, consider the following example: let $Q=T[H_1, H_2]$, where $T$ is a 2-cycle, $|V(H_1)|=1$, $|V(H_2)|\geq 3$ and $V(H_2)$ induces an independent set of $Q$. It can be checked that $Q$ does not contain an acyclic spanning subdigraph $R$ with a source $x$ and a sink $y$ such that for each vertex $z$ of $Q$, $R$ contains an $x-z$ path and a $z-y$ path. This means that not all strong semicomplete compositions contain such a subdigraph. Hence, it is interesting to study the following question.

\[op3\]Characterize strong semicomplete compositions $Q$ which contain an acyclic spanning subdigraph $R$ with a source $x$ and a sink $y$ such that for each vertex $z$ of $Q$, $R$ contains an $x-z$ path and a $z-y$ path.

Arc-disjoint in-and out-branchings
----------------------------------

Edmonds @Edmonds characterized digraphs with $k$ arc-disjoint out-branchings rooted at a specified vertex $r.$ Furthermore, there exists a polynomial algorithm for finding $k$ arc-disjoint out-branchings with a given root $r$ if they exist @Bang-Jensen-Gutin. However, it is NP-complete to decide whether a digraph $D$ has a pair of arc-disjoint out-branching and in-branching rooted at $r,$ which was proved by Thomassen (see @Bang-Jensen). Following @Bang-Jensen-Huang2014 we will call such a pair a <span>*good pair rooted at $r$*</span>. Note that a good pair forms a strong spanning subdigraph of $D$ and thus if $D$ has a good pair, then $D$ is strong. The problem of the existence of a good pair was studied for tournaments and their generalizations, and characterizations (with proofs implying polynomial-time algorithms for finding such a pair) were obtained in @Bang-Jensen for tournaments, @Bang-Jensen-Huang1 for quasi-transitive digraphs and @Bang-Jensen-Huang2014 for locally semicomplete digraphs. Also, Bang-Jensen and Huang @Bang-Jensen-Huang1 showed that if $r$ is adjacent to every vertex of $D$ (apart from itself) then $D$ has a good pair rooted at $r$.

In @Gutin-Sun, Gutin and Sun studied the existence of good pairs for digraph compositions. By Theorem \[sss2\], they got the following lemma.

\[ass3\]@Gutin-Sun Let $Q=T[H_1,\dots ,H_t],$ where $t\ge 2.$ If $T$ has a Hamiltonian cycle and $H_1,\dots ,H_t$ are arbitrary digraphs, each with at least two vertices, then $Q$ has a good pair at any root $r$.

An <span>*ear decomposition*</span> of a digraph $D$ is a sequence $\mathcal{P}=(P_0, P_1, P_2, \cdots, P_t)$, where $P_0$ is a cycle or a vertex and each $P_i$ is a path, or a cycle with the following properties:\
$(a)$ $P_i$ and $P_j$ are arc-disjoint when $i\neq j$.\
$(b)$ For each $i=0,1,2,\cdots,t$: let $D_i$ denote the digraph with vertices $\bigcup_{j=0}^i{V(P_j)}$ and arcs $\bigcup_{j=0}^i{A(P_j)}$. If $P_i$ is a cycle, then it has precisely one vertex in common with $V(D_{i-1})$. Otherwise the end vertices of $P_i$ are distinct vertices of $V(D_{i-1})$ and no other vertex of $P_i$ belongs to $V(D_{i-1})$.\
$(c)$ $\bigcup_{j=0}^t{A(P_j)}=A(D)$.

The following result on ear decomposition is well-known, see e.g., @Bang-Jensen-Gutin.

\[ass01\] Let $D$ be a digraph with at least two vertices. Then $D$ is strong if and only if it has an ear decomposition. Furthermore, if $D$ is strong, every cycle can be used as a starting cycle $P_0$ for an ear decomposition of $D$, and there is a linear-time algorithm to find such an ear decomposition.

By Lemma \[ass3\] and Theorem \[ass01\], Gutin and Sun furthermore got the following result.

\[ass4\]@Gutin-Sun Let $Q=T[\overline{K}_2, \dots, \overline{K}_2],$ where $|V(T)|=t\ge 2$ and $\overline{K}_2$ is the digraph with two vertices and no arcs. If $T$ is strong, then $Q$ has a good pair at any root $r$.

By Lemmas \[ass3\] and \[ass4\], and Theorem \[ass01\], Gutin and Sun obtained a sufficient condition under which a digraph composition has a good pair at any root $r$.

\[ass5\]@Gutin-Sun Let $Q=T[H_1,\dots ,H_t],$ where $t\ge 2.$ If $T$ is strong and $H_1,\dots ,H_t$ are arbitrary digraphs, each with at least two vertices, then $Q$ has a good pair at any root $r$. Furthermore, this pair can be found in polynomial time.

The condition of $n_i\ge 2$ in Theorem \[ass5\] cannot be relaxed. Indeed, the following characterization of quasi-transitive digraphs with a good pair provides an infinite family of strong quasi-transitive digraphs which have no good pair rooted at some vertices.

\[ass02\]@Bang-Jensen-Huang1 Let $D$ be a strong quasi-transitive digraph and $r$ a vertex of $D$ such that $V(D)=\{r\}\cup N^-(r)\cup N^+(r)$. There is a polynomial-time algorithm to decide whether $D$ has a good pair at $r$.

Gutin and Sun characterized semicomplete compositions with a good pair, which generalizes the corresponding characterization in Theorem \[ass02\].

\[ass6\]@Gutin-Sun A strong semicomplete composition $Q$ has a good pair rooted at $r$ if and only if $Q'=Q[\{r\}\cup N^-(r)\cup N^+(r)]$ has a good pair rooted at $r$.

By Theorems \[ass02\] and \[ass6\], we immediately have the following:

\[ass7\]@Gutin-Sun Given a semicomplete composition and a vertex $r$, we can decide in polynomial time whether $D$ has a good pair rooted at $r.$

Recall that Theorem \[ass6\] generalizes a similar characterization by Bang-Jensen and Huang @Bang-Jensen-Huang1 for quasi-transitive digraphs. Strong semicomplete compositions is not the only class of digraphs generalizing strong quasi-transitive digraphs. Other such classes have been studied such as $k$-quasi-transitive digraphs @GSHC and it would be interesting to see whether a characterization for the problem (or, at least non-trivial sufficient conditions) on $k$-quasi-transitive digraphs can be obtained.

\[op5\]@Gutin-Sun Characterize $k$-quasi-transitive digraphs with a good pair at any root $r$.

As we mentioned above, Bang-Jensen and Huang @Bang-Jensen-Huang2014 obtained a characterization for the problem for locally semicomplete digraphs. It would be interesting to see whether a characterization for the problem on locally in-semicomplete digraphs can be obtained.

\[op6\]@Gutin-Sun Characterize locally in-semicomplete digraphs with a good pair at any root $r$.

It is worth mentioning a related question. An out-branching and in-branching $B^+_r$ and $B^-_r$ are called $k$-<span>*distinct*</span> if $B^+_r$ has at least $k$ arcs not present in $B^-_r.$ The problem of deciding whether a digraph $D$ has a $k$-distinct pair of out- and in-branchings is NP-complete since it generalizes the good pair problem ($k=|V(D)|-1$). Bang-Jensen and Yeo @bangDAM156 asked whether the $k$-distinct problem is fixed-parameter tractable when parameterized by $k$, i.e., whether there is an $O(f(k)|V(D)|^{O(1)})$-time algorithm for solving the problem, where $f(k)$ is an arbitrary computable function in $k$ only. Gutin, Reidl and Wahlstr<span>ö</span>m @gutinJCSS95 answered this open question in affirmative by designing an $O(2^{O(k\log^2 k)}|V(D)|^{O(1)})$-time algorithm for solving the problem.

Strong spanning subdigraphs {#sec:sss}
===========================

Strong spanning subdigraphs without a 2-cycle
---------------------------------------------

The following result on strong semicomplete digraphs can be found in the literature, see e.g. Proposition 2.2.8 of @Bang-Jensen-Havet.

\[sss01\] Every strong semicomplete digraph on $n \geq 3$ vertices contains a strong spanning tournament.

Theorem \[sss01\] means that every strong semicomplete digraph on $n \geq 3$ vertices contains a strong spanning semicomplete digraph without a 2-cycle. Bang-Jensen and Huang obtained a similar result for strong quasi-transitive digraphs.

\[sss02\]@Bang-Jensen-Huang1 Every strong quasi-transitive digraph contains a strong spanning quasi-transitive digraph without a 2-cycle.

Sun got a similar result to Theorem \[sss02\] for strong semicomplete compositions.

\[sss1\]@Sun2 A strong semicomplete composition $Q=T[H_1, \dots, H_t]$ contains a strong spanning semicomplete composition without a 2-cycle if and only if $t\geq 3$.

Smallest strong spanning subdigraph
-----------------------------------

For a digraph $D$ and a natural number $k$, let $H_k(D)$ denote a digraph obtained from $D$ as follows: add two sets of $k$ new vertices $x_1, x_2, \dots, x_k$, $y_1, y_2, \dots, y_k$; add all possible arcs from $V(D)$ to $x_i$ along with all possible arcs from $y_i$ to $V(D)$, $i\in [k]$; add all arcs of the kind $x_iy_j$, $i, j \in [k]$. Clearly, $H_0(D)= D$. Let $D$ be a strong connected digraph and let $\epsilon(D)$ be the smallest $k \geq 0$ such that $H_k(D)$ is Hamiltonian. Observe that $$\epsilon(D)=\left\{
   \begin{array}{ll}
     0, &\mbox {$D$ is Hamiltonian;}\\
     pc(D), &\mbox {Otherwise.}
   \end{array}
   \right.$$

The <span>*smallest strong spanning subdigraph*</span> of a digraph $D$ is defined to be the strong spanning subdigraph of $D$ with smallest arcs. The problem of <span>Smallest Strong Spanning Subdigraph</span> (SSSS) is defined as follows: given a strong digraph $D$, find a strong spanning subdigraph $D'$ of $D$ such that $D'$ has as few arcs as possible. This problem generalizes the Hamiltonian cycle problem (and therefore is NP-hard) and has been considered in the literature, see e.g. @Aho-Garey-Ullman [@Bang-Jensen-Huang-Yeo; @Khuller-Raghavachari-Young].

In particular, Bang-Jensen, Huang and Yeo obtained the following result on the smallest strong spanning subdigraph of a strong quasi-transitive digraph.

\[sss03\]@Bang-Jensen-Huang-Yeo The smallest strong spanning subdigraph of a strong quasi-transitive digraph $D$ has precisely $n+\epsilon(D)$ arcs.

In the argument of Theorem \[sss03\], the authors used the following two lemmas.

\[BHY2003-1\]@Bang-Jensen-Huang-Yeo If $D$ is an acyclic extended semicomplete digraph, then $pc(D)= \max\{|I| \mid I~is~an~independent~set~in~D\}$. Furthermore, starting from $D$, one can obtain a path covering with $pc(D)$ paths by removing the vertices of a longest path $pc(D)$ times.

\[BHY2003-2\]@Bang-Jensen-Huang-Yeo Let $D$ be a strong extended semicomplete digraph and let $C$ be a longest cycle in $D$. Then $D-V(C)$ is acyclic.

By Theorems \[cycle1\], Lemmas \[BHY2003-1\] and \[BHY2003-2\], Sun extended Theorem \[sss03\] to strong semicomplete compositions.

\[sss8\]@Sun2 The smallest strong spanning subdigraph of a strong semicomplete composition $Q=T[H_1, \dots, H_t]$ has precisely $n+\epsilon(Q)$ arcs.

Strong arc decomposition
------------------------

Recall that it is NP-complete to decide whether a digraph $D$ has a pair of arc-disjoint out-branching and in-branching rooted at $r,$ which was proved by Thomassen (see @Bang-Jensen). In connection with this problem, Thomassen @Thomassen posed the following conjecture: There exists an integer $N$ so that every $N$-arc-strong digraph $D$ contains a pair of arc-disjoint in- and out-branchings. A digraph $D=(V,A)$ has a <span>*strong arc decomposition*</span> if $A$ has two disjoint sets $A_1$ and $A_2$ such that both $(V,A_1)$ and $(V,A_2)$ are strong @Bang-Jensen-Gutin-Yeo. Bang-Jensen and Yeo @Bang-Jensen-Yeo generalized [^1] the above conjecture as follows: There exists an integer $N$ so that every $N$-arc-strong digraph $D$ has a good decomposition. For a general digraph $D$, it is NP-complete to decide whether a digraph has a strong arc decomposition @Bang-Jensen-Gutin-Yeo. In the same paper, Bang-Jensen and Yeo characterized semicomplete digraphs with a strong arc decomposition. Bang-Jensen and Huang @Bang-Jensen-Huang extended this result by characterizing locally semicomplete digraphs with such a decomposition. After that, Sun, Gutin and Ai @Sun-Gutin-Ai continued research on strong arc decompositions in classes of digraphs and consider digraph compositions and products.

The following theorem gives sufficient conditions for a digraph composition to have a strong arc decomposition. We use $S_4$ to denote the digraph obtained from the complete digraph with four vertices by deleting a cycle of length 4, as shown in Figure \[S4fig\].

=\[circle,draw, top color=gray!5, bottom color=gray!30, minimum size=16pt, scale=0.6, inner sep=0.5pt\] =\[circle,draw, top color=gray!5, bottom color=gray!30, minimum size=20pt, scale=0.7, inner sep=1.5pt\]

\[scale=0.4\] (v1) at (1.0,6.0) \[vertexX\] <span>$v_1$</span>; (v2) at (7.0,6.0) \[vertexX\] <span>$v_2$</span>; (v3) at (1.0,1.0) \[vertexX\] <span>$v_3$</span>; (v4) at (7.0,1.0) \[vertexX\] <span>$v_4$</span>; (v1) – (v2); (v2) – (v3); (v3) – (v4); (v4) – (v1); (v1) to \[out=285, in=75\] (v3); (v3) to \[out=105, in=255\] (v1); (v2) to \[out=285, in=75\] (v4); (v4) to \[out=105, in=255\] (v2);

\[sss2\]@Sun-Gutin-Ai Let $T$ be a digraph with vertices $u_1,\dots ,u_t$ ($t\ge 2$) and let $H_1,\dots ,H_t$ be digraphs. Let the vertex set of $H_i$ be $\{u_{i,j_i}\colon\, 1\le i\le t, 1\le j_i\le n_i\}$ for every $i\in [t].$ Then $Q=T[H_1,\dots ,H_t]$ has a strong arc decomposition if at least one of the following conditions holds:

(a) 

:   $T$ is a 2-arc-strong semicomplete digraph and $H_1,\dots , H_t$ are arbitrary digraphs, but $Q$ is not isomorphic to $S_4;$

(b) 

:   $T$ has a Hamiltonian cycle and one of the following conditions holds:

    -   $t$ is even and $n_i\ge 2$ for every $i=1,\dots ,t;$

    -   $t$ is odd, $n_i\ge 2$ for every $i=1,\dots ,t$ and at least two distinct subdigraphs $H_i$ have arcs;

    -   $t$ is odd and $n_i\ge 3$ for every $i=1,\dots ,t$ apart from one $i$ for which $n_i\ge 2$.

(c)

:   $T$ and all $H_i$ are strong digraphs with at least two vertices.

They used Theorem \[sss2\] to prove the following characterization for semicomplete compositions $T[H_1,\dots ,H_t]$ when each $H_i$ has at least two vertices.

\[sss3\]@Sun-Gutin-Ai Let $Q=T[H_1,\dots ,H_t]$ be a strong semicomplete composition such that each $H_i$ has at least two vertices for $i\in [t]$. Then $Q$ has a strong arc decomposition if and only if $Q$ is not isomorphic to one of the following three digraphs: $\overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_2]$, $\overrightarrow{C}_3[\overrightarrow{P_2},\overline{K}_2,\overline{K}_2]$, $\overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_3].$

Bang-Jensen, Gutin and Yeo solved an open problem in @Sun-Gutin-Ai by obtaining a characterization of all semicomplete compositions with a strong arc decomposition. Note that a digraph with a strong arc decomposition is 2-arc-strong.

\[sss4\]@Bang-Jensen-Gutin-Yeo Let $Q=T[H_1,\dots ,H_t]$ be a semicomplete composition. Then $Q$ has a strong arc decomposition if and only if $Q$ is 2-arc-strong and is not isomorphic to one of the following four digraphs: $S_4$, $\overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_2]$, $\overrightarrow{C}_3[\overrightarrow{P_2},\overline{K}_2,\overline{K}_2]$, $\overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_3].$

Among their argument, the main technical result is the following theorem.

\[sss4-1\]@Bang-Jensen-Gutin-Yeo Let $Q=T[\overline{K}_{n_1}, \dots,\overline{K}_{n_t}]$ be an extended semicomplete digraph where $n_i\leq 2$ for $i\in [t]$. If $Q$ is 2-arc-strong, then $Q$ has a strong arc decomposition if and only if $Q$ is not isomorphic to one of the following four digraphs: $S_4$, $\overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_2]$, $\overrightarrow{C}_3[\overrightarrow{P_2},\overline{K}_2,\overline{K}_2]$.

Theorems \[intro01\] and \[sss4\] imply a characterization of quasi-transitive digraphs with a strong arc decomposition (this solves another open question in @Sun-Gutin-Ai).

\[sss5\]@Bang-Jensen-Gutin-Yeo A quasi-transitive digraph $D$ has a strong arc decomposition if and only if $D$ is 2-arc-strong and is not isomorphic to one of the following four digraphs: $S_4$, $\overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_2]$, $\overrightarrow{C}_3[\overrightarrow{P_2},\overline{K}_2,\overline{K}_2]$, $\overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_3].$

All proofs in @Bang-Jensen-Gutin-Yeo are constructive and can be turned into polynomial algorithms for finding strong arc decompositions. Thus, the problem of finding a strong arc decomposition in a semicomplete composition, which has one, admits a polynomial time algorithm.

Recall that strong semicomplete compositions generalize both strong semicomplete digraphs and strong quasi-transitive digraphs. However, they do not generalize locally semicomplete digraphs and their generalizations in- and out-locally semicomplete digraphs. While there is a characterization of locally semicomplete digraphs having a strong arc decomposition @Bang-Jensen-Huang, no such a characterization is known for locally in-semicomplete digraphs and it would be interesting to obtain such a characterization or at least establish the complexity of deciding whether an locally in-semicomplete digraph has a strong arc decomposition.

\[op7\]@Bang-Jensen-Gutin-Yeo Can we decide in polynomial time whether a given locally in-semicomplete digraph has a strong arc decomposition?

\[op8\]@Bang-Jensen-Gutin-Yeo Characterize locally in-semicomplete digraphs with a strong arc decomposition.

The following two types of strong subgraph packing problems could be seen as natural extensions of the problem of strong arc decomposition. Let $D=(V(D),A(D))$ be a digraph of order $n$, $S\subseteq V$ a $k$-subset of $V(D)$ and $2\le k\leq n$. A strong subgraph $H$ of $D$ is called an <span>*$S$-strong subgraph*</span> if $S\subseteq V(H)$. Two $S$-strong subgraphs are said to be <span>*arc-disjoint*</span> if they have no common arc. Furthermore, two arc-disjoint $S$-strong subgraphs are said <span>*internally disjoint*</span> if the set of common vertices of them is exactly $S$. The input of <span>Arc-disjoint strong subgraph packing</span> (ASSP) consists of a digraph $D$ and a subset of vertices $S\subseteq V(D)$, the goal is to find a largest collection of arc-disjoint $S$-strong subgraphs. Similarly, the input of <span>Internally-disjoint strong subgraph packing</span> (ISSP) consists of a digraph $D$ and a subset of vertices $S\subseteq V(D)$, and the goal is to find a largest collection of internally disjoint $S$-strong subgraphs.

Some results on the above strong subgraph packing problems and related topics have been obtained in @Sun-Gutin2 [@Sun-Gutin-Yeo-Zhang; @Sun-Jin; @Sun-Zhang] (also can be found in a recent survey @Sun-Gutin3). Especially, Sun and Zhang gave two sufficient conditions for a digraph composition to have at least $n_0$ arc-disjoint $S$-strong subgraphs for any $S\subseteq V(Q)$ with $2\leq |S|\leq |V(Q)|$. Recall that $n_0=\min\{n_i\mid 1\leq i\leq t\}$.

\[sss6\]@Sun-Zhang The digraph composition $Q=T[H_1,\dots, H_t]$ has at least $n_0$ arc-disjoint $S$-strong subgraphs for any $S\subseteq V(Q)$ with $2\leq |S|\leq |V(Q)|$, if one of the following conditions holds:

(a) 

:   $D$ is a strong symmetric digraph;

(b) 

:   $D$ is a strong semicomplete digraph and $Q\not\in
    \mathcal{Q}_0$, where\
    $\mathcal{Q}_0=\{\overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_2], \overrightarrow{C}_3[\overrightarrow{P}_2,\overline{K}_2,\overline{K}_2], \overrightarrow{C}_3[\overline{K}_2,\overline{K}_2,\overline{K}_3]\}$.

Moreover, these strong subgraphs can be found within time complexity $O(n^4)$, where $n$ is the order of $Q$.

By Theorems \[intro01\] and \[sss6\], we directly have:

\[sss7\]@Sun-Zhang Let $Q\not\in \mathcal{Q}_0$ be a strong quasi-transitive digraph. We can in polynomial time find at least $n_0$ arc-disjoint $S$-strong subgraphs in $Q$ for any $S\subseteq V(Q)$ with $2\leq |S|\leq |V(Q)|$.

<span>**Acknowledgement.**</span> Yuefang Sun was supported by Zhejiang Provincial Natural Science Foundation (No. LY20A010013).

<span>99</span>

A.V. Aho, M.R. Garey and J.D. Ullman, The transitive reduction of a directed graph, SIAM J. Comput. 1(2), 1972, 131–137.

A. Arroyo and H. Galeana-Sánchez, The Path Partition Conjecture is true for some generalizations of tournaments, Discrete Math. 313, 2013, 293–300.

J. Bang-Jensen, On the 2-linkage problem for semicomplete digraphs, Ann. Discrete Math. 41, 1989, 23–38.

J. Bang-Jensen, Edge-disjoint in- and out-branchings in tournaments and related path problems, J. Combin. Theory Ser. B 51(1), 1991, 1–23.

J. Bang-Jensen, Linkages in locally semicomplete digraphs and quasi-transitive digraphs, Discrete Math. 196, 1999, 13–27.

J. Bang-Jensen, Locally semicomplete digraphs and generalizations, in <span>*Classes of Directed Graphs*</span> (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018.

J. Bang-Jensen, Y. Guo, G. Gutin and L. Volkmann, A classification of locally semicomplete digraphs, Discrete Math. 167/168, 1997, 101–114.

J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd Edition, Springer, London, 2009.

J. Bang-Jensen, G. Gutin and J. Huang, A sufficient condition for a complete multipartite digraph to be hamiltonian, Discrete Math. 161, 1996, 1–12.

J. Bang-Jensen, G. Gutin and A. Yeo, Arc-disjoint strong spanning subgraphs of semicomplete compositions, J. Graph Theory 95(2), 2020, 267–289.

J. Bang-Jensen and F. Havet, Tournaments and semicomplete digraphs, in <span>*Classes of Directed Graphs*</span> (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018.

J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20(2), 1995, 141–161.

J. Bang-Jensen and J. Huang, Kings in quasi-transitive digraphs, Discrete Math. 185, 1998, 19–27.

J. Bang-Jensen and J. Huang, Decomposing locally semicomplete digraphs into strong spanning subdigraphs, J. Combin. Theory Ser. B 102, 2012, 701–714.

J. Bang-Jensen and J. Huang, Arc-disjoint in- and out-branchings rooted at the same vertex in locally semicomplete digraphs, J. Graph Theory 77, 2014, 278–298.

J. Bang-Jensen, J. Huang and A. Yeo, Strongly connected spanning subgraphs with the minimum number of arcs in quasi-transitive digraphs, SIAM J. Discrete Math. 16, 2003, 335–343.

J. Bang-Jensen, M.H. Nielsen, Minimum cycle factors in quasi-transitive digraphs, Discrete Optimization, 5, 2008, 121–137.

J. Bang-Jensen, M.H. Nielsen and A. Yeo, Longest path partitions in generalizations of tournaments, Discrete Math. 306(16), 2006, 1830–1839.

J. Bang-Jensen and A. Yeo, Decomposing $k$-arc-strong tournaments into strong spanning subdigraphs, Combinatorica 24(3), 2004, 331–349.

J. Bang-Jensen and A. Yeo, The minimum spanning strong subdigraph problem is fixed parameter tractable. Discrete Appl. Math. 156, 2008, 2924–2929.

M. Bezem, C. Grabmayer and M. Walicki, Expressive power of digraph solvability, Ann. Pure Appl. Logic, 163(3), 2012, 200–213.

J.A. Bondy, Basic graph theory: paths and circuits, in <span>*Handbook of Combinatorics*</span>, Vol.1/2, pages 3–110. Elsevier, Amsterdam, 1995.

J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, Berlin, 2008.

E. Boros and V. Gurvich, Perfect graphs, kernels, and cores of cooperative games, Discrete Math. 306(19), 2006, 2336–2354.

V. Chvátal, On the computational complexity of finding a kernel, Technical Report Centre de Recherches Mathématiques, Université de Montréal CRM-300, 1973.

V. Chvátal and L. Lovász, Every directed graph has a semi-kernel, Lect Notes in Math. 411, 1974, 175–175.

J. Edmonds, Edge-disjoint branchings, in <span>*Combinatorial Algorithms*</span> (B. Rustin ed.), Academic Press, 1973, 91–96.

A.S. Fraenkel, Planar kernel and Grundy with $d\leq 3$, $d^+\leq 2$, $d^-\leq 2$ are NP-complete, Discrete Appl. Math. 3, 1981, 257–262.

H. Galeana-Sánchez and C. Hernández-Cruz, Quasi-transitive digraphs and their extensions, in <span>*Classes of Directed Graphs*</span> (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018.

H. Galeana-Sánchez, B. Llano and J. Montellano-Ballesteros, $k$-colored kernels, Discrete Appl. Math. 160(13-14), 2012, 1971–1978.

H. Galeana-Sánchez and J. Montellano-Ballesteros, Richardson's Theorem for $k$-colored kernels in strongly connected digraphs, Discrete Appl. Math. 203, 2016, 47–52.

T. Gallai, On directed paths and circuits, in: Colloq. Tihany, vol. 1996, Academic Press, New York, 1968.

G. Gutin, Cycles and paths in directed graphs, PhD thesis, School of Mathematics, Tel Aviv University, 1993.

G. Gutin, Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math. 6, 270–273, 1993.

G. Gutin, Polynomial algorithms for finding Hamiltonian paths and cycles in quasi-transitive digraphs, Australas. J. Combin. 10, 1994, 231–236.

G. Gutin, Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs, Discrete Math. 141(1-3), 1995, 153–162.

G. Gutin, K.M. Koh, E.G. Tay and A. Yeo, On the number of quasi-kernels in digraphs, J. Graph Theory 46, 2004, 48–56.

G. Gutin, F. Reidl and M. Wahlstr<span>ö</span>m, $k$-Distinct in- and out-branchings in digraphs, J. Comput. Syst. Sci. 95, 2018, 86–97.

G. Gutin and Y. Sun, Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs, Discrete Math. 343(5), 2020, 111816.

G. Gutin and A. Yeo, Kings in semicomplete multipartite digraphs, J. Graph Theory 33, 2000, 177–183.

R.H. Hammack, Digraph products, in <span>*Classes of Directed Graphs*</span> (J. Bang-Jensen and G. Gutin, eds.), Springer, 2018.

S. Heard and J. Huang, Disjoint quasi-kernels in digraphs, J. Graph Theory, 58(3), 2008, 251–260.

P. Hell and C. Hernández-Cruz, On the complexity of the 3-kernel problem in some classes of digraphs, Discuss. Math. Graph Theory 34, 2014, 167–185.

J. Huang and W. Li, Toppling kings in a tournament by introducing new kings, J. Graph Theory 11, 1987, 7–11.

S. Khuller, B. Raghavachari and N. Young, Approximating the minimum equivalent digraph, SIAM J. Comput. 24, 1995, 859–872.

K.M. Koh and B.P. Tan, Number of 4-kings in bipartite tournaments with no 3-kings, Discrete Math. 154(1–3), 1996, 281–287.

K.M. Koh and B.P. Tan, The number of kings in a multipartite tournament, Discrete Math. 167/168, 1997, 411–418.

J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, Teubner-Texte Math. 59, 1983, 173–177. H.G. Landau, On dominance relations and the structure of animal societies III, The condition for a score structure, Bull. Math. Biophys. 15, 1953, 143–148.

S.B. Maurer, The king chicken theorems, Math. Mag. 53(2), 1980, 67–80.

K.B. Reid, Every vertex a king, Discrete Math. 38, 1982, 93–98.

B. Roy, Nombre chromatique et plus longs chemins d'un graphe, Rev. Française Informat. Recherche Operátionnelle 1(5), 1967, 129–132.

B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory Ser. B 33(3), 1982, 271–275.

M. Shen, On monochromatic paths in m-coloured tournaments, J. Combin. Theory Ser. B 45(1), 1988, 108–111.

Y. Sun, Kings and kernels in semicomplete compositions, arXiv:2006.05607v3 \[math.CO\] 21 Feb 2021.

Y. Sun, Semicomplete compositions of digraphs, arXiv:2005.01050v1 \[math.CO\] 3 May 2020.

Y. Sun, Disjoint paths and cycles in compositions of digraphs, in preparation.

Y. Sun, G. Gutin, Strong subgraph connectivity of digraphs: a survey, submitted.

Y. Sun, G. Gutin, Strong subgraph connectivity of digraphs, Graphs Combin. doi:10.1007/s00373-021-02294-w.

Y. Sun, G. Gutin and J. Ai, Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs, Discrete Math. 342(8), 2019, 2297–2305.

Y. Sun, G. Gutin, A. Yeo and X. Zhang, Strong subgraph $k$-connectivity, J. Graph Theory 92(1), 2019, 5–18.

Y. Sun and Z. Jin, Minimally strong subgraph $(k,\ell)$-arc-connected digraphs, Discuss. Math. Graph Theory, doi:10.7151/dmgt.2301.

Y. Sun and X. Zhang, Complexity and computation of strong subgraph packing in digraphs, submitted.

C. Thomassen, Configurations in graphs of large minimum degree, connectivity, or chromatic number, Ann. New York Acad. Sci. 555, 1989, 402–412.

C. Thomassen, Hamiltonian-connected tournaments, J. Combin. Theory Ser. B 28, 1980, 142–163.

L.M. Vitaver, Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix, Dokl. Akad. Nauk SSSR 147, 1962, 758.

L. Volkmann, Cycles in multipartite tournaments: results and problems, Discrete Math. 245(1), 2002, 19–53.

J. von Neumann and O. Morgenstern, <span>*Theory of Games and Economic Behavior*</span>, Princeton University Press, Princeton, NJ, 1944.

M. Walicki and S. Dyrkolbotn, Finding kernels or solving SAT, J. Discrete Algorithms, 10, 2012, 146–164.

R. Wang and H. Zhang, $(k+1)$-kernels and the number of $k$-kings in $k$-quasi-transitive digraphs, Discrete Math. 338(1), 2015, 114–121.

[^1]: Every strong digraph $D$ has an out- and in-branching rooted at any vertex of $D$.

{'source': 'arXiv_out/2103'}