A kernel \(J\) of a digraph \(D\) is an independent set of vertices of \(D\) such that for every \(z\in V(D)\backslash J\) there exists an arc from \(z\) to \(J.\) A digraph \(D\) is said to be kernel-perfect if every induced subdigraph of it has a kernel. We characterise kernel-perfectness in special families of digraphs, namely, the line digraph, the subdivision digraph, the middle digraph, the digraph \(R(D)\) and the total digraph. We also obtain some results on kernel-perfectness in the generalised Mycielskian of digraphs. Moreover, we find some new classes of kernel-perfect digraphs by introducing a new product on digraphs.
Throughout this paper, \(D=(V(D),A(D))\) denotes a finite digraph with no loops, no parallel arcs, and no isolates (isolates are vertices with in-degree and out-degree zero), where \(V(D)\) (resp. \(A(D)\)) is the vertex set (resp. the arc set) of \(D.\) A walk, path, and cycle, respectively, denote a directed walk, directed path, and directed cycle. A walk, path, or cycle is called even (resp. odd) if its length is even (resp. odd). An arc \(xy\in A(D)\) is symmetric, if \(yx\in A(D).\) A digraph \(D\) is said to be complete symmetric if there is a symmetric arc between any pair of vertices of \(D.\) We call a digraph bipartite (resp. connected) if its underlying graph is bipartite (resp. connected). A digraph with no cycles is called acyclic.
Let \(C=v_0v_1\dots v_{n-1}v_0\) be a cycle of \(D.\) Two vertices joined by an arc of \(C\) are said to be consecutive on \(C.\) A chord of \(C\) is an arc of \(D\) of the form \(v_iv_j\) with \(j\not\equiv (i+1)(\)mod\(~n).\) The chord \(v_iv_j\) is short when \(j\equiv (i+2)(\)mod\(~n).\) The endpoints of chords of \(C\) are called poles of \(C.\)
For \(X,Y\subseteq V(D),\) \(\left[X,Y\right]\) denotes the set of all arcs of \(D\) with tail in \(X\) and head in \(Y;\) an arc \((x,y)\) of \(D\) will be called an \((X,Y)\)- arc whenever \(x\in X\) and \(y \in Y.\) When \(X = \{u\},\) we will simply write \((u,Y)\)- arc and analogously we write \((X, v)\)- arc if \(Y = \{v\}.\)
A kernel \(J\) of a digraph \(D\) is an independent set of vertices of \(D\) such that for every vertex \(z\in V (D)\backslash J\) there exists an arc from \(z\) to a vertex in \(J.\)
A semikernel of a digraph \(D\) is an independent set \(S\) of vertices of \(D\) such that for every \(z\in V(D)\backslash S\) for which there exists an \((S,z)\)- arc there also exists an \((z,S)\)- arc in \(D.\) Note that a kernel of \(D\) is a semikernel of \(D.\) Furthermore, for any digraph \(D,\) if \(X_0=\{x\in V(D)|\) there exists \(y\in N_D^+(x)\) with \(N_D^+(y)\subseteq N_D^+(x)\},\) then, for any semikernel \(S\) of \(D,\) \(S\cap X_0=\emptyset.\)
A digraph \(D\) is said to be kernel-perfect (KP- digraph) if every induced subdigraph of \(D\) has a kernel. A digraph which is not kernel-perfect is called kernel-imperfect.
Many structural properties of digraphs that give rise to kernel-perfect digraphs have been explored widely. It is important to note that deciding the kernel-perfectness of a digraph is co-\(\mathcal{NP}\)-hard (see [1]).
We list some classical sufficient conditions for a digraph to be kernel-perfect.
Theorem 1.1 (Richardson [12]). A digraph with no odd cycle is kernel-perfect.
Below are some independent generalisations of Theorem 1.1.
Theorem 1.2 (Duchet [4]).If \(D\) is a digraph such that every odd cycle possesses at least two symmetric arcs, then \(D\) is kernel-perfect.
Theorem 1.3 (Duchet [4]). If every cycle of a digraph \(D\) has a symmetric arc, then \(D\) is kernel-perfect.
Theorem 1.4 (Duchet [4]). If every odd cycle of a digraph \(D\) has two short chords and the directed triangles are symmetric, then \(D\) is kernel-perfect.
Theorem 1.5 (Galeana-Sánchez and Neumann-Lara [4]). If every odd cycle of a digraph \(D\) has two consecutive poles on the cycle, then \(D\) is kernel-perfect.
Theorem 1.6(Neumann-Lara [11]). If every induced subdigraph of a digraph \(D\) has a nonempty semikernel, then \(D\) is kernel-perfect.
For some more sufficient conditions, see [2], [7] and [8].
A digraph \(D\) is called transitive, if \(uw\in A(D),\) whenever \(uv,vw\in A(D).\) Some generalisations of transitive digraphs were introduced in [4] and [9]. Let \(D\) be a digraph; \(D\) is quasi-transitive, if \(uv,vw\in A(D)\) implies that \(uw\in A(D)\) or \(wu\in A(D);\) \(D\) is right-pretransitive (resp. left-pretransitive), if \(uv,vw\in A(D)\) implies that \(uw\in A(D)\) or \(wv\in A(D)\) (resp. \(uw\in A(D)\) or \(vu\in A(D)\)). Note that if \(D\) is transitive, then every induced subdigraph of \(D\) is also transitive. Similar property holds for quasi-transitive, left-pretransitive and right-pretransitive digraphs.
The line digraph \(L(D)\) has vertex set \(V(L(D))=A(D)\) and arc set \(A(L(D))=\{ab:a,b\in V(L(D)),\) the head of \(a\) coincides with the tail of \(b\) in \(D\}.\)
Let \(D\) be a digraph. For distinct elements \(a,b\in V(D)\cup A(D),\) consider the following possibilities:
(1) \(a\in V(D),\) \(b\in V(D)\) and \(ab\in A(D);\)
(2) \(a\in V(D),\) \(b\in A(D)\) and \(a\) coincides with the tail of arc \(b\) in \(D;\)
(3) \(a\in A(D),\) \(b\in V(D)\) and \(b\) coincides with the head of arc \(a\) in \(D;\)
(4) \(a\in A(D),\) \(b\in A(D)\) and \(ab\in A(L(D)).\)
With the vertex set as \(V(D)\cup A(D),\) four operations on digraphs, namely, the subdivision digraph \(S(D),\) the middle digraph \(Q(D),\) the digraph \(R(D),\) and the total digraph \(T(D)\) are introduced in [13] with their arc sets defined as below:
\(\bullet\) \(ab\in A(S(D))\) if, and only if, the pair \((a,b)\) satisfies (2) or (3);
\(\bullet\) \(ab\in A(Q(D))\) if, and only if, the pair \((a,b)\) satisfies (2) or (3) or (4);
\(\bullet\) \(ab\in A(R(D))\) if, and only if, the pair \((a,b)\) satisfies (1) or (2) or (3);
\(\bullet\) \(ab\in A(T(D))\) if, and only if, the pair \((a,b)\) satisfies (1) or (2) or (3) or (4).
From the definitions, observe that \(Q(D)=S(D)\cup L(D),\) \(R(D)=D\cup S(D)\) and \(T(D)=D\cup S(D)\cup L(D).\)
In [13], the author obtained some necessary or sufficient conditions for the existence or uniqueness of kernels in digraphs formed by the above four operations.
The generalised Mycielskian \(\mu_m(D)\) of a loopless digraph \(D=(V^0,A^0)\) is defined, in [6], as the digraph whose vertex set is \(V^0\cup V^1\cup \dots \cup V^m\cup \{u\},\) where \(V^i=\{v^i:v^0\in V^0\},\) \(i=1,2,\dots,m,\) and arc set \(A^0\cup \Big(\bigcup \limits_{i=0}^{m-1} \{x^i y^{i+1},~x^{i+1} y^i:x^0y^0 \in A^0\}\Big)\cup \{x^{m}u,~ux^{m}:x^m\in V^m\}.\)
Given a digraph \(D_1,\) a symmetric digraph \(D_2,\) and a subset \(Y\subseteq V(D_2),\) we define the product \(D_1\times_{Y} D_2\) as follows:
(i) \(V(D_1\times_{Y} D_2)=V(D_1)\times V(D_2);\)
(ii) \((u_1,v_1)\rightarrow (u_2,v_2)\) in \(D_1\times _{Y}D_2\) if \(u_1\rightarrow u_2\) in \(D_1\) and \(v_1\rightarrow v_2\) in \(D_2;\) and
(iii) for every \(v\in Y,\) \((u_1,v)\rightarrow (u_2,v)\) in \(D_1\times _{Y}D_2\) if \(u_1\rightarrow u_2\) in \(D_1.\)
The significance of introducing this product is to yield a new class of KP-digraphs \(D_1\times _Y D_2\) from certain known choices of KP-digraphs \(D_1.\) Also, note that: \(D_1\times_Y D_2\) is the tensor product \(D_1\times D_2,\) when \(Y=\emptyset;\) \(D_1\times_Y D_2\) is \(\mu_m(D_1)-u,\) when \(D_2\) is the symmetric path \(v_0v_1\dots v_m\) and \(Y=\{v_0\}.\)
For notation not defined here, see [3].
In Section 2, we prove some preliminary results that are used in Sections 4 and 5. In Section 3, kernel-perfectness is characterised in digraphs \(L(D),\) \(S(D),\) \(Q(D),\) \(R(D)\) and \(T(D).\) In Section 4, we identify certain families of kernel-perfect digraphs \(D\) such that \(\mu_m(D)\) is kernel-perfect. Specifically, in Theorem 4.2 (resp. in Theorems 4.5 and 4.6), we identify some special families of KP-digraphs \(D\) such that \(\mu_m(D)\) belongs to the special family of KP-digraphs to which the corresponding \(D\) belongs (resp. \(\mu_m(D)\) is kernel-perfect but \(\mu_m(D)\) does not belong to the special family of KP-digraphs to which the corresponding \(D\) belongs). In Section 5, we provide some sufficient conditions on \(D_1\) for \(D_1\times_{Y} D_2\) to be kernel-perfect.
In this section, we give some basic results that will be used in Sections 4 and 5.
Lemma 2.1. In a quasi-transitive digraph, each vertex of a kernel (if exists) acts as a nonempty semikernel of it.
Proof. Let \(D\) be a quasi-transitive digraph with a kernel \(J.\) Let \(x\in J.\) If \(d_D^+(x)=0,\) then \(\{x\}\) is a semikernel of \(D.\) So, assume \(d_D^+(x)\ge 1.\) Let \(z\in N_{D}^+(x).\) Clearly, \(z\in V(D)\backslash J.\) As \(J\) is a kernel of \(D,\) there exists \(y\in J\) such that \(z\rightarrow y.\) If \(y\ne x,\) then, as \(x\rightarrow z\rightarrow y,\) the quasi-transitivity implies that \(x\rightarrow y\) or \(y\rightarrow x,\) a contradiction. Thus \(y=x\) and so \(z\in N_{D}^-(x).\) Hence \(N_{D}^+(x)\subseteq N_{D}^-(x).\) Therefore, \(\{x\}\) is a semikernel of \(D.\) ◻
The above result is true for transitive digraphs and left-pretransitive digraphs. But it is not the case for right-pretransitive digraphs. To see this, consider the complete symmetric digraph \(K_n^*\) with \(V(K_n^*)=\{x_1,x_2,\dots,x_n\}.\) Form \(D\) from \(K_n^*\) by adding new vertices \(y_1,y_2,\dots,y_n\) and arcs \(y_1x_1,y_2x_2,\dots,y_nx_n.\) Clearly, \(D\) is right-pretransitive, but it is neither left-pretransitive nor quasi-transitive. Here, \(J=\{x_1,y_2,y_3,\dots,y_n\}\) is a kernel of \(D,\) but no vertex of \(J\backslash \{x_1\}\) is a semikernel of \(D.\)
Lemma 2.2. If \(D\) is right-pretransitive or left-pretransitive or transitive, then every cycle of \(D\) has a symmetric arc.
Proof. First, let \(D\) be a right-pretransitive digraph. Suppose \(D\) has cycles with no symmetric arcs. Let \(C\) be a shortest such cycle. Let \(C:v_0v_1v_2\dots v_{t-1}v_0,\) where the suffixes in \(v_i\) are reduced modulo \(t.\) Since \(v_0v_{1},v_{1}v_{2}\in A(D)\) and \(v_{1}v_{2}\) is not symmetric, by the right-pretransitivity of \(D,\) we have \(v_0v_2\in A(D).\) If \(v_0v_2\) is not symmetric, then \(v_0v_2v_3\dots v_{t-1}v_0\) is a cycle of \(D\) with no symmetric arc, a contradiction to the choice of \(C.\) So \(v_0v_2\) is a symmetric arc (i.e., \(v_2v_0\) is also an arc of \(D\)). Now, since \(v_2v_{0},v_{0}v_{1}\in A(D)\) and neither of \(v_0v_1\) and \(v_1v_2\) is symmetric, we have a contradiction to the right-pretransitivity of \(D.\)
Similar proof holds if \(D\) is left-pretransitive, considering the arcs \(v_1v_2\) and \(v_2v_0.\) As every transitive digraph is both right-pretransitive and left-pretransitive, it is evident that every cycle of a transitive digraph has a symmetric arc. ◻
The above result need not be true for quasi-transitive digraphs. To see this, let \(D\) be a digraph with \(V(D)=\{x,y,v_1,v_2,\dots,v_{n-2}\}\) and \(A(D)=\{yx\}\cup \{xv_i,v_iy~:~i\in \{1,2,\dots,n-2\}\}.\) Clearly, \(D\) is quasi-transitive but none of the cycles of \(D\) has a symmetric arc.
The following result is a consequence of Lemma 2.2.
Theorem 2.3. Let \(H_1\) and \(H_2\) be digraphs (\(A(H_1)\cap A(H_2)\) may be non-empty). If \(D=H_1\cup H_2\) with \(H_1\) and \(H_2\) as its induced subdigraphs, then, in any of the following cases, every cycle of \(D\) has a symmetric arc:
(1) \(H_1\) is right-pretransitive and \(H_2\) is left-pretransitive;
(2) both \(H_1\) and \(H_2\) are left-pretransitive or right-pretransitive;
(3) every cycle of \(H_1\) has a symmetric arc and \(H_2\) is left-pretransitive or right-pretransitive.
Proof. (1) Proof is by contradiction. Suppose \(D\) has cycles with no symmetric arcs. Let \(C\) be a shortest such cycle. Let \(C:v_0v_1v_2\dots v_{t-1}v_0,\) where the suffixes in \(v_i\) are reduced modulo \(t.\) If \(C\) has two consecutive arcs in \(H_1\) or in \(H_2,\) then, from the proof of Lemma 2.2, we have a contradiction. So \(t\) is even and \(C\) alternates its arcs in \(H_1\) and \(H_2.\) As \(v_i\in V(H_1)\cap V(H_2)\) for every \(i\in \{0,1,2,\dots,t-1\}\) and \(H_1,\) \(H_2\) are induced subdigraphs of \(D,\) we have that \(C\) is contained in \(H_1\) and in \(H_2,\) a contradiction.
For (2), the proof is similar to that of (1).
(3) Assume that every cycle of \(H_1\) has a symmetric arc. First, we prove this result if \(H_2\) is left-pretransitive. Proof is by contradiction. Let \(C\) be a shortest cycle in \(D\) such that no arc of \(C\) is symmetric. Let \(C:v_0v_1v_2\dots v_{t-1}v_0,\) where the suffixes in \(v_i\) are reduced modulo \(t.\) As in the proof of Lemma 2.2, if \(C\) has two consecutive arcs in \(H_2,\) then we have a contradiction. So no two consecutive arcs of \(C\) are in \(H_2.\) As \(v_i\in V(H_1)\) for every \(i\in \{0,1,2,\dots,t-1\},\) we have that \(C\) is in \(H_1,\) a contradiction.
Proof for right-pretransitive digraph \(H_2\) follows in a similar way. ◻
Regarding the presence of kernels in digraphs obtained by some unary operations from other digraphs, many authors had previously investigated. For example, see [5], [10] and [13]. In this section, we characterise the kernel-perfectness of digraphs \(L(D),\) \(S(D),\) \(Q(D),\) \(R(D)\) and \(T(D)\).
It merits attention that the line digraph is a well-known and extensively studied operation. Harminc characterised the existence of a kernel in \(L(D)\) as below:
Theorem 3.1(Harminc [10]). \(D\) has a kernel if, and only if, \(L(D)\) has a kernel.
As a natural progression to the above theorem, we characterise the kernel-perfectness of \(L(D)\) in Theorem 3.4, which carries a deep significance but its proof is delightfully simple.
Observation 3.2. If \(D\) has an odd cycle, then \(L(D)\) has an induced odd cycle.
Observation 3.3. If \(L(D)\) has an odd cycle, then \(D\) has an odd cycle.
Consider a kernel-perfect digraph \(D\) with an odd cycle. From Observation 3.2, we see that \(L(D)\) has an induced odd cycle, which is a kernel-less induced subdigraph. Hence, even if \(D\) is kernel-perfect, \(L(D)\) need not be. From Observations 3.2 and 3.3 along with Theorem 1.1, we have:
Theorem 3.4. \(L(D)\) is kernel-perfect if, and only if, \(D\) has no odd cycles.
Observation 3.5. For any digraph \(D,\) \(S(D)\) is bipartite and hence is kernel-perfect.
While considering \(Q(D)\) and \(R(D),\) take \(W=V(D)\) and \(Z=V(L(D)).\) Here, \(\{W,Z\}\) is a partition of each of \(V(Q(D))\) and \(V(R(D)).\)
Theorem 3.6. \(Q(D)\) is kernel-perfect if, and only if, \(D\) has no odd cycles.
Proof. From the definition of \(Q(D),\) \(L(D)\) is an induced subdigraph of \(Q(D).\) By Theorem 3.4, for \(Q(D)\) to be kernel-perfect, it is necessary that \(D\) must be free of odd cycles. So the necessity follows. To prove the sufficiency, we prove that every induced subdigraph of \(Q(D)\) has a kernel, when \(D\) has no odd cycles. Observe that \(L(D)\) is kernel-perfect. Let \(H\) be an induced subdigraph of \(Q(D).\) If \(Z\cap V(H)\) is empty, then \(H\) has no arcs and therefore it has a kernel. Let \(X=W\cap V(H)\) and \(Y=W\setminus V(H).\) If \(X\) is empty, then \(H\) is an induced subdigraph of the kernel-perfect digraph \(L(D),\) and therefore \(H\) has a kernel. Hence, assume that both \(X\) and \(Z\cap V(H)\) are nonempty.
Let \[\begin{aligned} Z^H_{WX}=&\{(w,x)\in Z\cap V(H)\,|\,w\in W\text{ and }x\in X\},\\ Z^H_{XY}=&\{(x,y)\in Z\cap V(H)\,|\,x\in X\text{ and }y\in Y\}, \text{ and }\\ Z^H_{YY}=&\{(y,y')\in Z\cap V(H)\,|\,y,y'\in Y\}. \end{aligned}\]
Note that \(\{Z^H_{WX},Z^H_{XY},Z^H_{YY}\}\) is a partition of \(Z\cap V(H).\) In \(H\) (and also in \(Q(D)\!\)), the sets \(X\) and \(Z^H_{XY}\) are independent and the arc sets \(\left[X,Z^H_{YY}\right],\) \(\left[Z^H_{WX},Z^H_{YY}\right],\) \(\left[Z^H_{XY},X\right],\) \(\left[Z^H_{YY},X\right]\) and \(\left[Z^H_{YY},Z^H_{XY}\right]\) are empty.
Consider \(H\left[Z^H_{YY}\right],\) an induced subdigraph of \(H.\) As it is an induced subdigraph of the kernel-perfect digraph \(L(D),\) it has a kernel, say, \(K_1.\) Clearly, \(K_1\) absorbs \(Z^H_{YY}\setminus K_1.\) Now, let \(A_1\) be the set of vertices in \(Z^H_{XY}\) that are absorbed by \(K_1\) in \(H\) (\(A_1\) may be empty). Let \(K_2=Z^H_{XY}\setminus A_1.\) Since \(Z_{XY}^H\) is independent and \(\left[Z^H_{YY},Z^H_{XY}\right]=\emptyset,\) we have \(K_1\cup K_2\) is independent in \(H.\) Also, it absorbs \((Z^H_{YY}\setminus K_1)\cup A_1.\) Next, let \(A_2\) be the set of vertices in \(X\) that are absorbed by \(K_2\) in \(H\) (\(A_2\) may be empty). Take \(K_3=X\setminus A_2.\) Note that, the set \(K=K_1\cup K_2\cup K_3\) is independent in \(H,\) as \(X\) is independent and the arc sets \(\left[X,Z^H_{YY}\right],\) \(\left[Z^H_{YY},X\right]\) and \(\left[Z^H_{XY},X\right]\) are empty. Clearly, \(K\) absorbs \((Z^H_{YY}\setminus K_1)\cup A_1\cup A_2\) in \(H.\) Further, if we show that \(K\) absorbs \(Z^H_{WX},\) then \(K\) will become a kernel of \(H.\) Let \((w,x)\in Z^H_{WX},\) where \(w\in W\) and \(x\in X.\) Clearly, \((w,x)\rightarrow x\) in \(H.\) As \(X\) is a disjoint union of \(K_3\) and \(A_2,\) either \(x\in K_3\) or \(x\in A_2.\) If \(x\in K_3,\) then, in \(H,\) \((w,x)\) is absorbed by \(x,\) a vertex of \(K.\) If \(x\in A_2,\) then by the definition of \(A_2,\) there exists \(y\in Y\) such that \(x\rightarrow (x,y)\) and \((x,y)\in K_2,\) where \(K_2\subseteq Z^H_{XY}.\) Therefore, in \(H,\) we have \((w,x)\rightarrow (x,y),\) where \((x,y)\in K.\) This completes the proof. ◻
Lemma 3.7. If \(D_0\) is a digraph having an independent set \(I\) such that (i) for any three vertices \(x\notin I,\) \(y\in I,\) \(z\notin I,\) if \(x\to y\to z,\) then \(x\to z;\) and (ii) \(D~=~D_0\setminus I\) is kernel-perfect, then \(D_0\) is kernel-perfect.
Proof. Let \(H\) be an induced subdigraph of \(D_0.\) If \(V(H)\cap I\) is empty, then \(H\) is an induced subdigraph of the kernel-perfect digraph \(D,\) and therefore \(H\) has a kernel. If \(V(H)\cap V(D)\) is empty, then \(H\) has no arcs and hence it has a kernel. So, assume that both \(V(H)\cap I\) and \(V(H)\cap V(D)\) are nonempty.
Let \(K_1'=\{v\in V(H)\cap I\,:\, d_H^+(v)=0\}\cup \{v\in V(H)\cap I\,:\, d_H^-(v)\ge 1\mathrm{~and~}d_H^+(v)\ge 1\}.\) As \(K_1'\subseteq I,\) \(K_1'\) is independent. Let \(A_1\) be the set of vertices of \(D\cap H\) that are absorbed by \(K_1'\) (\(A_1\) may be empty). Consider the subdigraph \((D\cap H)\setminus A_1.\) As it is an induced subdigraph of the kernel-perfect digraph \(D,\) it has a kernel, say, \(K_2.\) Clearly, \(\left[K_2,K_1'\right]=\emptyset.\) Consider \(\left[K_1',K_2\right].\) Let \(K_1''\) be the set of vertices in \(K_1'\) that are absorbed by \(K_2\) (note that \(K_1''=\emptyset\) when \(\left[K_1',K_2\right]=\emptyset\)). Set \(K_1=K_1'\setminus K_1''.\) As \(\left[K_1,K_2\right]=\emptyset,\) \(K_1\cup K_2\) is independent. We claim that the set of vertices of \(A_1\) that are absorbed by \(K_1''\) is absorbed by \(K_2\) also. To see this, let \(x\) be a vertex of \(A_1\) that is absorbed by a vertex \(y\) of \(K_1''.\) From the definition of \(K_1'',\) there exists \(z\in K_2\) such that \(y\rightarrow z\) in \(H.\) By (i), \(x\rightarrow z\) in \(H\) which proves the claim. Therefore, \(A_1\) is absorbed by \(K_1\cup K_2.\)
Now, \(K_1\cup K_2\) absorbs \(K_1''\cup (V(D\cap H)\setminus K_2),\) since \(K_2\) is a kernel of \((D\cap H)\backslash A_1.\) Let \(A_2\) be the set of vertices of \((V(H)\cap I)\setminus K_1'\) that are absorbed by \(K_2.\) Set \(K_3=(V(H)\cap I)\setminus (K_1'\cup A_2).\) From the definition of \(K_3,\) \(K_1\cup K_2\cup K_3\) is independent and hence is a kernel of \(H.\) ◻
Theorem 3.8. \(R(D)\) is kernel-perfect if, and only if, \(D\) is kernel-perfect.
Proof. As \(D\) is an induced subdigraph of \(R(D),\) for \(R(D)\) to be kernel-perfect, it is necessary that \(D\) is kernel-perfect. To prove the sufficiency, take \(D_0~=~R(D)\) and \(I\) to be the set of vertices of \(R(D)\) corresponding to the arcs of \(D,\) and apply Lemma 3.7. ◻
Theorem 3.9. \(T(D)\) is kernel-perfect if, and only if, \(D\) is acyclic.
Proof. Observe that \(T(D)\) has a cycle, if, and only if, \(D\) has a cycle. So, if \(D\) is acyclic, then \(T(D)\) is also acyclic and hence is kernel-perfect.
Conversely, suppose that \(D\) has a cycle, say, \(C.\) Let \(C:v_0v_1v_2\dots v_nv_0\) and let \(e_i=v_{i-1}v_i,\) \(i\in \{1,2,\dots,n\},\) and \(e_{n+1}=v_{n}v_{0}.\) Clearly, \(e_1e_2\dots e_{n+1}e_1\) is an induced \((n+1)\)- cycle in \(L(D)\) and so in \(T(D)\) also. As \(T(D)\) is kernel-perfect, \(n\) must be odd. If at least one arc of \(C\) is symmetric, say \(e_i\) is symmetric, then let \(e_i'=v_iv_{i-1}.\) Now, the subdigraph induced by \(\{v_{i-1},v_i,e_i,e_i'\}\) in \(T(D)\) is kernel-less, a contradiction. Hence, assume that every arc of \(C\) is asymmetric. Therefore, we have the induced odd cycle \(v_0v_1e_2e_3\dots e_ne_{n+1}v_0\) of length \((n+2)\) in \(T(D),\) which is again a contradiction to the kernel-perfectness of \(T(D).\) ◻
In this section, let the vertex set (resp. arc set) of \(D\) be denoted by \(V^0\) (resp. \(A^0\)) and the vertex set (resp. arc set) of \(\mu_m(D)\) be denoted by \(V\) (resp. \(A\)).
For \(X^0\subseteq V^0,\) set \(X^i=\{x^i:x^0\in X^0\}\subseteq V^i,\) for each \(i\in \{1,2,\dots,m\}.\)
As \(D\) is an induced subdigraph of \(\mu_m(D),\) if \(D\) is kernel-imperfect, then so is \(\mu_m(D).\) So, in what follows, we assume that \(D\) is kernel-perfect.
Even if \(D\) is kernel-perfect, \(\mu_m(D)\) may be kernel-imperfect. For example, let \(D'=C+\{v_0^0v_2^0,v_1^0v_3^0\},\) where \(C:v_0^0v_1^0\dots v_{2k}^0v_0^0,\) \(k\ge 3.\) By Theorem 1.4, \(D'\) is kernel-perfect. For \(m\ge 2,\) \(v_0^0v_1^1v_2^2v_3^1v_4^0v_5^0v_6^0\dots v_{2k-1}^0v_{2k}^0v_0^0\) is an induced odd cycle, and hence \(\mu_m(D')\) is kernel-imperfect. Here, \(D'\) also serves as an example to prove that neither of the sufficient conditions of Theorems 1.4 and 1.5 in \(D'\) is sufficient for \(\mu_m(D')\) to be kernel-perfect.
First, we shall see some sufficient conditions for kernel-perfectness of \(\mu_m(D).\)
Lemma 4.1. If \(D\) is a digraph such that every odd cycle in \(D\) possesses at least two symmetric arcs, then, in \(\mu_m(D)\) also, every odd cycle possesses at least two symmetric arcs.
Proof. Let \(C\) be an odd cycle in \(\mu_m(D).\) If \(C\) contains \(u,\) then \(C\) has at least two symmetric arcs (arcs incident at \(u\)). If \(C\) does not contain \(u,\) then \(C\) induces a closed odd walk, say, \(C'\) in \(D.\) As every closed odd walk contains an odd cycle, \(C'\) contains an odd cycle, say, \(C''\) in \(D.\) By hypothesis, \(C''\) has at least two symmetric arcs in \(D.\) The arcs in \(C\) corresponding to the two symmetric arcs of \(C''\) are symmetric in \(\mu_m(D)\) and hence \(C\) has at least two symmetric arcs in \(\mu_m(D).\) ◻
From Lemma 4.1 and Theorems 1.2 and 1.3, we have:
Theorem 4.2. For a digraph \(D,\) \(\mu_m(D)\) is kernel-perfect in each of the following cases:
(1) every odd cycle of \(D\) possesses at least two symmetric arcs;
(2) every cycle of \(D\) has a symmetric arc.
Corollary 4.3. If \(D\) is transitive or right-pretransitive or left-pretransitive, then \(\mu_m(D)\) is kernel-perfect.
Proof. Follows from Lemma 2.2 and (2) of Theorem 4.2. ◻
Corollary 4.4. \(\mu_m(D)\) is kernel-perfect, if \(D\) has no odd cycles. So does \(\mu_m(D)\) if \(D\) is bipartite.
Observe that \(\mu_m(D)\) is neither transitive nor quasi-transitive since \(V^m\rightarrow u\rightarrow V^m\) and \(V^m\) is independent.
Theorem 4.5. If \(D\) is a kernel-perfect quasi-transitive digraph, then \(\mu_m(D)\) is kernel-perfect.
Proof. Let \(H\) be an induced subdigraph of \(\mu_m(D).\) We prove that \(H\) has a nonempty semikernel. If \(\delta^+(H)=0\) (resp. \(u\in V(H)\)), then \(\{v\in V(H)~:~d_{H}^+(v)=0\}\) (resp. \(\{u\}\)) is a nonempty semikernel of \(H.\) Therefore, assume \(\delta^+(H)\ge 1\) and \(u\notin V(H).\) Let \(H^0\) denote the subdigraph of \(D\) induced by \(\{v^0~:~v^i\in V(H)\) for some \(i\in \{0,1,2,\dots,m\}\},\) which is clearly a nonempty set. As \(H^0\) is an induced subdigraph of \(D,\) \(H^0\) has a kernel \(J^0.\) Observe that \(\delta^+(H^0)\ge 1\) and \(H^0\) is quasi-transitive. Let \(x^0\in J^0.\) By Lemma 2.1, \(\{x^0\}\) is a semikernel of \(H^0\) and so, we have \(N_{H^0}^+(x^0)\subseteq N_{H^0}^-(x^0).\) As \(x^0\in V(H^0),\) there exists \(i\in \{0,1,2,\dots,m\}\) such that \(x^i\in V(H),\) which implies that \(N_{H}^+(x^i)\subseteq N_{H}^-(x^i).\) So \(\{x^i\}\) is a semikernel of \(H.\) Therefore, by Theorem 1.6, \(\mu_m(D)\) is kernel-perfect. ◻
Now, we consider right- or left- pretransitive digraphs. Observe that, for a right- (resp. left-) pretransitive digraph \(D\) with an asymmetrical arc, \(\mu_m(D)\) is not right- (resp. left-) pretransitive. Since, for an asymmetrical arc \(ab\in A(D),\) in \(\mu_m(D)\) we have: \(u\rightarrow a^m\rightarrow b^{m-1}\) with neither \(u\rightarrow b^{m-1}\) nor \(b^{m-1}\rightarrow a^{m},\) if \(D\) is right-pretransitive; \(a^{m-1}\rightarrow b^m\rightarrow u\) with neither \(a^{m-1}\rightarrow u\) nor \(b^{m}\rightarrow a^{m-1},\) if \(D\) is left-pretransitive. Thus observe that \(\mu_m(D)\) does not preserve the property of \(D.\) Hence, by Theorems 2.3 and 4.2 (2), we have:
Theorem 4.6. Let \(H_1\) and \(H_2\) be digraphs (\(A(H_1)\cap A(H_2)\) may be nonempty). If \(D=H_1\cup H_2\) with \(H_1\) and \(H_2\) as its induced subdigraphs, then \(\mu_m(D)\) is kernel-perfect in any of the following cases:
(1) \(H_1\) is right-pretransitive and \(H_2\) is left-pretransitive;
(2) both \(H_1\) and \(H_2\) are left-pretransitive or right-pretransitive;
(3) every cycle of \(H_1\) has a symmetric arc and \(H_2\) is left-pretransitive or right-pretransitive.
Next, we concentrate on giving a necessary condition for \(\mu_m(D)\) to be kernel-perfect. By Corollary 4.4, it is enough to consider digraphs with odd cycles. For an odd cycle \(C:v_0^0v_1^0\dots v_{2k}^0v_0^0\) in a digraph \(D,\) and for each \(i\in \{0,1,\dots,2k\},\) let \(C_i=\{(v_{i-\ell}^0,v_{i+\ell}^0):\,\ell=1,2,\dots,k-1\},\) where the subscripts in \(v_j^0\) are reduced modulo \(2k+1\) and the set \(C_i\) is a collection of arcs that are not necessarily present in \(D.\)
Theorem 4.7. Let \(D\) be a digraph with odd cycles, let \(c\) be the length of a longest odd cycle in \(D,\) and \(m\ge \frac{c-1}{2}.\) If \(\mu_m(D)\) is kernel-perfect, then, for every odd cycle \(C:v_0^0v_1^0\dots v_{2k}^0v_0^0\) of \(D,\) an arc of \(C\) is symmetric or for every \(i\in \{0,1,\dots,2k\},\) \(A^0\cap (C_{i-1}\cup C_i)\ne \emptyset.\)
Proof. Suppose \(D\) has an odd cycle \(C:v_0^0v_1^0\dots v_{2k}^0v_0^0\) such that no arc of \(C\) is symmetric and \(A^0\cap (C_{i-1}\cup C_i)=\emptyset\) for some \(i\in \{0,1,\dots,2k\}.\) We obtain a contradiction by finding an induced odd cycle in \(\mu_m(D).\) Corresponding to \(C,\) by the definition of \(\mu_m(D),\) we have an odd cycle \(C':v_i^0v_{i+1}^1v_{i+2}^2 \dots v_{i+k-1}^{k-1}v_{i+k}^{k}v_{i+k+1}^{k-1}v_{i+k+2}^{k-2}\dots v_{i+2k-1}^{1}v_{i+2k}^{0}v_i^0\) in \(\mu_m(D).\) Note that any chord of \(C'\) is of the form \((v_{i-\ell}^{\ell-1},v_{i+\ell}^\ell),\) \((v_{i+\ell}^\ell,v_{i-\ell}^{\ell-1}),\) \((v_{i-1-\ell}^\ell,v_{i-1+\ell}^{\ell-1})\) or \((v_{i-1+\ell}^{\ell-1},v_{i-1-\ell}^\ell)\) for some \(\ell\in \{1,2,\dots,k-1\}.\) Since \(A^0\cap (C_{i-1}\cup C_i)=\emptyset,\) \((v_{i-\ell}^0,v_{i+\ell}^0)\in C_i\) and \((v_{i-1-\ell}^0,v_{i-1+\ell}^0)\in C_{i-1},\) we have that any chord of \(C'\) is of the form \((v_{i+\ell}^\ell,v_{i-\ell}^{\ell-1})\) or \((v_{i-1+\ell}^{\ell-1},v_{i-1-\ell}^\ell).\) Let \(p\) be the least value of \(\ell\) for which \((v_{i+p}^p,v_{i-p}^{p-1})\) or \((v_{i-1+p}^{p-1},v_{i-1-p}^p)\) is a chord of \(C'.\) If \((v_{i+p}^p,v_{i-p}^{p-1})\) is a chord of \(C',\) then \(v_i^0v_{i+1}^1v_{i+2}^2\) \(\dots v_{i+p-1}^{p-1}v_{i+p}^{p}v_{i-p}^{p-1}v_{i-(p-1)}^{p-2}\dots v_{i-1}^0v_i^0\) is an induced odd cycle. If \((v_{i-1+p}^{p-1},v_{i-1-p}^p)\) is a chord of \(C',\) then \(v_i^0v_{i+1}^1v_{i+2}^2\dots\) \(v_{i+p-1}^{p-1}v_{i-p-1}^{p}v_{i-p}^{p-1}\dots v_{i-1}^0v_i^0\) is an induced odd cycle. In both the cases, \(\mu_m(D)\) has an induced odd cycle, which is a kernel-less subdigraph, a contradiction. ◻
Throughout this section, assume that \(D_1\) is a digraph, \(D_2\) is a symmetric digraph and the subset \(Y\subseteq V(D_2)\) is nonempty.
As \(D_1\) is an induced subdigraph of \(D_1\times_{Y} D_2,\) if \(D_1\) is kernel-imperfect, then so is \(D_1\times_{Y} D_2.\) So, in what follows, we assume that \(D_1\) is kernel-perfect.
Even if \(D_1\) is kernel-perfect, \(D_1\times_{Y} D_2\) may be kernel-imperfect. For example, let \(C:v_0v_1\dots v_{2n}v_0,\) \(n\ge 2,\) be an odd cycle. Take \(D_1=C+v_0 v_{2i}\) for some \(i\in \{1,2,\dots,n-1\},\) a symmetric digraph \(D_2,\) and \(Y,\) a proper subset of \(V(D_2).\) Clearly, \(D_1\) is kernel-perfect. Let \(y\in Y,\) \(x\in V(D_2)\backslash Y\) and \(xy,yx\in A(D_2).\) From the definition of \(D_1\times_{Y} D_2,\) we have an induced odd cycle \((v_0,x)\)\((v_1,y)\)\((v_2,y)\)\(\dots\) \((v_{2i-1},y)\)\((v_{2i},x)\)\((v_{2i+1},y)\)\((v_{2i+2},y)\)\(\dots\)\((v_{2n},y)\)\((v_0,x)\) in \(D_1\times_{Y} D_2.\) Hence \(D_1\times_{Y} D_2\) is kernel-imperfect.
Our intention is to search for kernel-perfect digraphs \(D_1\) so that \(D_1\times_Y D_2\) is kernel-perfect.
Theorem 5.1. Let \(D_1\) be a digraph, \(D_2\) be a symmetric digraph and \(Y,\) a proper subset of \(V(D_2).\) Then \(D_1\times_{Y} D_2\) is kernel-perfect if \(D_1\) satisfies at least one of the following properties:
(1) every odd cycle in \(D_1\) possesses at least two symmetric arcs;
(2) every cycle in \(D_1\) has a symmetric arc;
(3) transitive or right-pretransitive or left-pretransitive.
Proof. We prove it for \(D_1\) satisfying (1) by showing that every odd cycle in \(D_1\times_{Y} D_2\) possesses at least two symmetric arcs. Let \(C\) be an odd cycle in \(D_1\times_{Y} D_2.\) By the definition of \(D_1\times_{Y} D_2,\) there is a closed odd walk \(C'\) in \(D_1,\) which corresponds to the sequence of the first entries of the vertices of \(C.\) As every closed odd walk contains an odd cycle, \(C'\) contains an odd cycle \(C''\) in \(D_1.\) By hypothesis, \(C''\) has at least two symmetric arcs in \(D_1.\) The arcs in \(C\) corresponding to the two symmetric arcs of \(C''\) are symmetric in \(D_1\times_{Y} D_2\) and hence \(C\) has at least two symmetric arcs in \(D_1\times_{Y} D_2.\)
For \(D_1\) satisfying (2), proof is similar to that of (1).
For \(D_1\) satisfying (3), proof follows from Lemma 2.2 and (2). ◻
Observation 5.2. \(D_1\times_{Y} D_2\) need not be quasi-transitive, even if \(D_1\) is quasi-transitive (For, consider any path \(u_1\rightarrow u_2\rightarrow u_3\) of length \(2\) in \(D_1\) and any arc \(v_1v_2\) of the symmetric digraph \(D_2\) with \(v_1\notin Y.\) In \(D_1\times_Y D_2,\) \((u_1,v_1)\rightarrow (u_2,v_2)\rightarrow (u_3,v_1).\) Here, neither \((u_1,v_1)\rightarrow (u_3,v_1)\) nor \((u_3,v_1)\rightarrow (u_1,v_1).\)). Similarly, \(D_1\times_{Y} D_2\) need not be left-pretransitive (resp. right-pretransitive), even if \(D_1\) is left-pretransitive (resp. right-pretransitive).
From Theorems 2.3 and 5.1 (2), we have:
Theorem 5.3. Let \(H_1\) and \(H_2\) be digraphs (\(A(H_1)\cap A(H_2)\) may be nonempty). If \(D_1=H_1\cup H_2\) with \(H_1\) and \(H_2\) as its induced subdigraphs, \(D_2\) is a symmetric digraph, and \(Y,\) a proper subset of \(V(D_2),\) then \(D_1\times_{Y} D_2\) is kernel-perfect in any of the following cases:
(1) \(H_1\) is right-pretransitive and \(H_2\) is left-pretransitive;
(2) both \(H_1\) and \(H_2\) are left-pretransitive or right-pretransitive;
(3) every cycle of \(H_1\) has a symmetric arc and \(H_2\) is left-pretransitive or right- pretransitive.
Theorem 5.4. If \(D_1\) is a kernel-perfect quasi-transitive digraph, \(D_2\) is a symmetric digraph, and \(Y,\) a proper subset of \(V(D_2),\) then \(D_1\times_{Y} D_2\) is kernel-perfect.
Proof. Let \(H\) be an induced subdigraph of \(D_1\times_{Y} D_2.\) We show that \(H\) has a nonempty semikernel. If \(\delta^+(H)=0,\) then \(\{(u,v)\in V(H)~:~d_{H}^+((u,v))=0\}\) is a nonempty semikernel of \(H.\) So assume \(\delta^+(H)\ge 1.\) Let \(D_1'\) denote the subdigraph of \(D_1\) induced by \(\{u\in V(D_1)~:~(u,v)\in V(H)\) for some \(v\in V(D_2)\},\) which is clearly a nonempty set. Observe that \(\delta^+(D_1')\ge 1\) and \(D_1'\) is quasi-transitive. As \(D_1\) is kernel-perfect, \(D_1'\) has a kernel, say, \(J'.\) Let \(x\in J'.\) From the proof of Lemma 2.1, \(N_{D_1'}^+(x)\subseteq N_{D_1'}^-(x).\) As \(x\in V(D_1'),\) we have \((x,v)\in V(H)\) for some \(v\in Y.\) And so \(N_{H}^+((x,v))\subseteq N_{H}^-((x,v)).\) Therefore, \(\{(x,v)\}\) is a semikernel of \(H.\) By Theorem 1.6, \(D_1\times_{Y} D_2\) is kernel-perfect. ◻
The authors thank the referees for their valuable comments and suggestions, which greatly improved the quality of this work. The work of the second author was carried out during her Ph.D. at the Department of Mathematics, Annamalai University, Annamalainagar, India. She gratefully acknowledges the Department of Science & Technology and the Ministry of Science & Technology, Government of India, for the financial support provided under the DST-INSPIRE Fellowship (Fellow code: IF160650).