About (k,l)-kernels, semikernels and Grundy functions in partial line digraphs

Discussiones Mathematicae Graph Theory 39 (2019)855–866 doi:10.7151/dmgt.2104 ABOUT (k, l)-KERNELS, SEMIKERNELS AND GRUNDY FUNCTIONS IN PARTIAL LINE DIGRAPHS1 C. Balbuena Departament d’Enginyeria Civil i Ambiental Universitat Polit´ Zcnica de Catalunya Campus Nord, Edifici C2, C/ Jordi Girona 1 i 3 E-08034 Barcelona, Spain e-mail: [email protected] H. Galeana-S´ anchez Instituto de Matem´aticas Universidad Nacional Aut´onoma de M´exico Ciudad Universitaria, Circuito Exterior 04510 M´exico D.F., M´exico e-mail: [email protected] and M. Guevara Facultad de Ciencias, Universidad Nacional Aut´onoma de M´exico Circuito Exterior S/N, Cd. Universitaria, Delegaci´on Coyoac´an 04510 M´exico D.F., M´exico e-mail: mucuy-kak.guev[email protected] Abstract Let Dbe a digraph of minimum in-degree at least 1. We prove that for any two natural numbers k, l such that 1 ≤l≤k, the number of (k, l)-kernels of Dis less than or equal to the number of (k, l)-kernels of any partial line digraph LD. Moreover, if l < k and the girth of Dis at least l+1, then these two numbers are equal. We also prove that the number of semikernels of Dis equal to the number of semikernels of LD. Furthermore, we introduce the concept of (k, l)-Grundy function as a generalization of the concept of 1This research was supported by the Ministerio de Educaci´on y Ciencia, Spain, the European Regional Development Fund (ERDF) under project MTM2014-60127-P, by CONACyT-M´exico under project 219840 and by UNAM-DGAPA-PAPIIT IN104717 and IN115816. 856 C. Balbuena, H. Galeana-S´ anchez and M. Guevara Grundy function and we prove that the number of (k, l)-Grundy functions of Dis equal to the number of (k, l)-Grundy functions of any partial line digraph LD. Keywords: digraphs, in-domination, kernel, Grundy function. 2010 Mathematics Subject Classification: 05C20, 05C69, 05C76. 1. Introduction Throughout the paper, D= (V, A) denotes a loopless digraph with vertex set Vand arc set A. Let ω−(x) stand for the set of arcs having vertex xas their terminal vertex, and ω+(x) stand for the set of arcs having vertex xas their initial vertex. Thus, the in-degree of xis d−(x) = |ω−(x)|and the out-degree of xis d+(x) = |ω+(x)|. The minimum in-degree (minimum out-degree) of D is δ−(D) = min{d− D(x) : x∈V}(δ+(D) = min{d+ D(x) : x∈V}respectively). Moreover, given a set U⊆V,ω−(U) = {(x, y)∈A:y∈Uand x /∈U}. Given a set of arcs Ω ⊆A, the heads of Ω are the vertices in the set H(Ω) = {y: (x, y)∈ Ω}. For any pair of vertices x, y ∈V, a directed path (x, x1,...,xn−1, y) from x to yis called an x→ypath. The distance from xto yis denoted by dD(x, y) and it is defined to be the length of a shortest x→ypath. A set K⊂V(D) is said to be a kernel if it is both independent (for every two vertices x, y ∈K,dD(x, y)≥2) and absorbing (a vertex not in Khas a successor in K). This concept was first introduced in [13] by Von Neumann and Morgensten in the context of Game Theory as a solution for cooperative n-player games. The concept of a kernel is important to the theory of digraphs because it arises naturally in applications such as Nim-type games, logic, and facility location, to name a few. Several authors have been investigating sufficient conditions for the existence of kernels in digraphs, for a comprehensive survey see for example [4] and [7]. Also see Chapter 15 of [12] for a summary. Let l, k be two integers such that l≥1 and k≥2. A (k, l)-kernel of a digraph Dis a subset of vertices Kwhich is both k-independent (dD(u, v)≥kfor all u, v ∈K) and l-absorbing (dD(x, K)≤lfor all x∈V\K). Observe that any kernel is a (2,1)-kernel and a quasikernel, introduced in [10], is a (2,2)-kernel. The concept of (k, l)-kernel is a nice and wide generalization of the concept of kernel; (k, l)-kernels have been deeply studied by several authors, see for example [8,9,18–20]. Grundy functions are very useful in the context of game theory and they are nearly related to kernels since a digraph with Grundy function has also a kernel. Also the concept of semikernel is very close to that of kernel, because a digraph such that every induced subdigraph has a nomempty semikernel has a kernel. The line digraph technique is a good general method for obtaining large digraphs with fixed degree and diameter. In the line digraph L(D) of a digraph (k, l)-Kernels, Semikernels and Grundy Functions 857 D, each vertex represents an arc of D. Thus, V(L(D)) = {uv : (u, v)∈A(D)}, and a vertex uv is adjacent to a vertex xz if and only if v=x, that is, when the arc (u, v) is adjacent to the arc (x, z) in D. For any h > 1, the h-iterated line digraph,Lh(D), is defined recursively by Lh(D) = L(Lh−1(D)). For more information about line digraphs see, for instance, Aigner [1], Fiol, Yebra and Alegre [5] and Reddy, Kuhl, Hosseini and Lee [17]. A wider family of digraphs, called partial line digraphs, was introduced in [6] as a generalization of line digraphs. Let D= (V, A) be a digraph and consider an arc subset A′⊆Aand a surjective mapping φ:A→A′such that (i) the set of heads of A′is H(A′) = V; (ii) the map φfixes the elements of A′, that is, φ|A′=id, and for every vertex j∈V,φ(ω−(j)) ⊂ω−(j)∩A′. Hence, |V| ≤ |A′| ≤ |A|. Note that the existence of such a subset A′is guaranteed when δ−(i)≥1 for every i∈V. Then, the partial line digraph of D, denoted by L(A′,φ)D(for short LDif the pair (A′, φ) is clear from the context), is the digraph with vertex set V(LD) = A′and set of arcs A(LD) = {(ij, φ((j, k))) : (j, k)∈A}. Remark 1. If A′=A, then φ=id and the partial line digraph LDcoincides with the line digraph L(D). In what follows we write φ(jk) instead φ((j, k)) for clarity. Figure 1 shows an example of a digraph Dwith 12 arcs and its partial line digraph with |A′|= 9 vertices. The arcs not in A′are drawn with dotted lines and have images φ(12) = 42, φ(34) = 54, and φ(65) = 25. 1 36 2 45 φ(12) = 42 φ(34) = 54 φ(65) = 25 21 56 43 25 54 42 36 1361 Figure 1. A digraph and its partial line digraph. 858 C. Balbuena, H. Galeana-S´ anchez and M. Guevara In this paper we study the relationship between the number of (k, l)-kernels (respectively, semikernels) of a digraph Dand the corresponding number in any partial line digraph LD. Also we introduce the concept of (k, l)-Grundy function as a generalization of the concept of Grundy function and we prove that the number of (k, l)-Grundy functions of Dis equal to the number of (k, l)-Grundy functions of any partial line digraph LD. 2. (k, l)-Kernels and Semikernels In this section we will prove that the number of (k, l)-kernels of a digraph is less than or equal to the number of (k, l)-kernels of its partial line digraphs, and under certain conditions these two numbers are equal. We start by proving a result concerning independent sets of a digraph and of those of their partial line digraphs. Lemma 2. Let Dbe a digraph with minimum in-degree at least 1. Let A′and φ satisfy the requirements of the definition of a partial line digraph, i.e., L(A′,φ)D= LD. Let k≥2be an integer number. Denote by Ithe set of all k-independent sets of D, and by I∗the set of all k-independent sets of LD. Then the assignment f:I → I∗defined by f(I) = ω−(I)∩A′for all I∈ I is an injective function. Therefore the number of k-independent sets of Dis less than or equal to the number of k-independent sets of LD. Proof. First of all let us see that fis a function. Let ab, cd ∈ω−(I)∩A′be such that dLD(ab, cd) = t, and observe that dD(b, d)≥kbecause b, d ∈I. By definition of φany shortest path from ab to cd in LDis ab, φ(bb1), φ(b1b2),...,φ(bt−1bt) = cd, where bi∈V(D) and (b, b1),(bi, bi+1)∈A(D), i= 1,...,t −1. Since φ(bt−1bt) = αbtfor some α∈V(D), then bt=dyielding that a walk b, b1,...,bt= dfrom bto dof length texists in D. This means that t≥dD(b, d)≥kand hence every two vertices of ω−(I)∩A′are mutually at distance at least k. Let us prove that fis an injective function. Let I1, I2∈ I be such that f(I1) = f(I2), that is ω−(I1)∩A′=ω−(I2)∩A′. Let us show that I1=I2. Let u∈I1. Note that by item (i) of definition of LDthere is y∈V(D) such that yu ∈A′. Clearly, yu ∈ω−(I1)∩A′which implies that yu ∈ω−(I2)∩A′, then u∈I2, that is, I1⊆I2. Reasoning analogously, I2⊆I1yielding that I1=I2. Therefore fis an injective function and the lemma holds. The concept of Fibonacci number for a graph Gwas introduced in [15] and it is defined as the number of independent subsets of Gincluding the empty set. We extend this concept for digraphs, and we give an upper bound on the Fibonacci number of a digraph in terms of the Fibonacci number of its partial line digraph. (k, l)-Kernels, Semikernels and Grundy Functions 859 Corollary 3. Let Dbe a digraph with minimum in-degree at least 1. Let A′ and φsatisfy the requirements of the definition of a partial line digraph, i.e., L(A′,φ)D=LD. Then the Fibonacci number of Dis less than or equal to the Fibonacci number of LD. 2.1. (k, l)-kernels Some known results about the existence of kernels and (k, l)-kernels in line digraphs can be seen in [11,16]. The following theorem is proved in [2]. Theorem 4 [2].Let k, l be two natural numbers such that 1≤l < k, and let D be a digraph with minimum in-degree at least 1and girth at least l+ 1. Then D has a (k, l)-kernel if and only if any partial line digraph LDhas a (k, l)-kernel. Note that, since a kernel is a (2,1)-kernel, it follows that Dhas a kernel if and only if any partial line digraph LDhas a kernel. Next, we establish a relationship between the number of (k, l)-kernels of Dand the number of (k, l)-kernels of LD. Theorem 5. Let k, l be two natural numbers such that l≥1and k≥2, and let Dbe a digraph with minimum in-degree at least 1. Let A′and φsatisfy the requirements of the definition of a partial line digraph, i.e., L(A′,φ)D=LD. Then the number of (k, l)-kernels of Dis less than or equal to the number of (k, l)-kernels of LD. Moreover, if l < k and the girth of Dis at least l+ 1, then these numbers are equal. Proof. Denote by Kthe set of all (k, l)-kernels of D, and by K∗denote the set of all (k, l)-kernels of LD. Let f:K → K∗be defined by f(K) = ω−(K)∩A′for all K∈ K. In the proof of Theorem 2.1 of [2] it was proved that fis well defined. And from Lemma 2 it follows that fis injective. Therefore |K| ≤ |K∗|. Let h:K∗→ K be defined by h(ˆ K) = H(ˆ K) for all ˆ K∈ K∗. In the proof of Theorem 2.1 of [2] it was proved that his well defined if l < k and the girth of Dis at least l+ 1. Moreover, we can check that h=f−1because h(f(K)) = H(ω−(K)∩A′) = K. Therefore the theorem holds. Corollary 6. Let Dbe a digraph with minimum in-degree at least 1. Let A′ and φsatisfy the requirements of the definition of a partial line digraph, i.e., L(A′,φ)D=LD. Then the following assertions hold. (i) The number of kernels of Dis equal to the number of kernels of LD. (ii) The number of quasikernels of Dis less than or equal to the number of quasikernels of LD. Let us observe that the number of quasikernels of Dcan be strictly less than the number of quasikernels of its line digraph L(D). A quasikernel is a (2,2)- kernel as we mentioned before, i.e., k=l= 2. The digraphs shown in Figure 2 860 C. Balbuena, H. Galeana-S´ anchez and M. Guevara have different number of quasikernels. This proves that the hypothesis l < k of Theorem 5 cannot be avoided to guarantee that the number of quasikernels of Dand L(D) is equal. In this example the digraph Don the left side has 3 quasikernels, namely, {x},{z}and {y, t}, while its line digraph on the right side has 5 quasikernels which are {zx},{tz, yz},{xy, xt},{xt, yz}and {xy, tz}. x zy t xy zxyz tz xt Figure 2. A digraph with 3 quasikernels and its line digraph with 5 quasikernels. 2.2. Semikernels Let Sbe an independent set of D. We say that Sis a semikernel of Dif for all sx ∈ω+(S) there exists xs′∈ω−(S). Thus, a vertex of out-degree zero forms a semikernel. Also a vertex only incident with symmetric arcs forms a semikernel. Figure 3 depicts a digraph having a semikernel but not a kernel. In [14] it was proved that if every induced subdigraph of Dhas a (nonempty) semikernel, then every induced subdigraph of Dhas a kernel, and so D. x Figure 3. A digraph with semikernel {x}but without kernels. In Theorem 2.1 of [10] it was proved that the number of semikernels of a digraph with minimum in-degree at least one is less than or equal to the number of semikernels of the line digraph. Next we improve and generalize this result by stating the equality for every partial line digraph. Theorem 7. Let Dbe a digraph with minimum in-degree at least 1. Let A′ and φsatisfy the requirements of the definition of a partial line digraph, i.e., L(A′,φ)D=LD. Then the number of semikernels of Dis less than or equal to the number of semikernels of LD. (k, l)-Kernels, Semikernels and Grundy Functions 861 Proof. Denote by Sthe set of all semikernels of D, and by S∗denote the set of all semikernels of LD. Let f:S → S∗be defined by f(K) = ω−(K)∩A′for all K∈ S. Let us see that f(K)∈ S∗. By Lemma 2, we know that fis an injective function and f(K) is an independent set. It remains to prove that if (e′, e)∈ω+(f(K)), then there exists (e, e′′)∈ω−(f(K)). Let (e′, e)∈ω+(f(K)). Then e′=x′y′∈f(K) = ω−(K)∩A′, yielding that y′∈K. Moreover, e=φ(y′y) because (e′, e)∈A(LD), which implies that (y′, y)∈ω+(K) since y′∈K. Since Kis a semikernel, there exists (y, y′′)∈ω−(K), implying e′′ =φ(yy′′)∈ω−(K)∩A′=f(K), then (e, e′′)∈ω−(f(K)), implying that f(K) is a semikernel. Figure 4 shows both a digraph and its line digraph with different number of semikernels. 1 2 3 4 5 6 3 45 6 12 Figure 4. A digraph with 4 semikernels and its line digraph, with 8 semikernels. Theorem 8. Let Dbe a digraph with minimum in-degree at least 1. Let A′ and φsatisfy the requirements of the definition of a partial line digraph, i.e., L(A′,φ)D=LD. Then LDhas a semikernel if and only if Dhas a semikernel. Proof. From Theorem 7 it follows that if Dhas a semikernel, then LDhas a semikernel. To see the converse let us consider the function h:S∗→ S defined by h(K∗) = H(K∗). First, let us see that H(K∗) is an independent set of D. Let u, v ∈H(K∗). Then u′u, v′v∈K∗for some u′, v′∈V(D), yielding that u′u, v′vare not adjacent in LD. We reason by contradiction assuming that uv ∈A(D). Then (u′u, φ(uv)) ∈ω+(K∗). Since K∗is a semikernel, there is (φ(uv), φ(vw)) ∈ω−(K∗). But v′v, φ(vw)∈K∗and they are adjacent which is a contradiction. Therefore u, v are not adjacent and so H(K∗) is independent. Second, vu ∈ω+(H(K∗)). As v∈H(K∗), there is v′v∈K∗and (v′v, φ(vu)) ∈ω+(K∗). Since K∗is a semikernel, it follows that there exists (φ(vu), φ(uw)) ∈ ω−(K∗). Then φ(uw)∈K∗and so w∈H(K∗). Therefore uw ∈ω−(H(K∗)) and the proof is finished. 862 C. Balbuena, H. Galeana-S´ anchez and M. Guevara 3. Grundy Function Definition. Consider a simple digraph D= (V, A). Following Berge [3], a nonnegative integer function gon Vis defined as a Grundy function if the following two requirements hold: (1) g(x) = k > 0 implies that for each j < k, there is y∈N+(x) with g(y) = j; (2) g(x) = kimplies that each y∈N+(x) satisfies g(y)6=k. This concept was first defined by Grundy in 1939 for acyclic digraphs as follows. For every x∈V,g(x) = min(N\ {g(y) : y∈N+(x)}). Furthermore, Grundy proved that every acyclic digraph has a unique Grundy function. However, there are digraphs without Grundy function, for instance the odd directed cycles. One of the most relevant properties of a Grundy function is that if Dhas a Grundy function g, then Dhas a kernel K={x∈V:g(x) = 0}. Next, we propose a generalization of a Grundy function called (k, l)-Grundy function. To do that we need to introduce some notation. The out-neighborhood at distance rfrom a vertex x∈Vis N+ r(x) = {y∈V: 1 ≤d(x, y)≤r}. Definition. Consider a simple digraph D= (V, A) and let l≥1 and k≥2 be two integers. A non-negative integer function gon Vis defined as a (k, l)-Grundy function if the following two requirements hold: (1) g(x) = t > 0 implies that for each j < t, there is y∈N+ l(x) with g(y) = j; (2) g(x) = timplies that each y∈N+ k−1(x) satisfies g(y)6=t. Figure 5 depicts on the left side a digraph with a (2,2)-Grundy function and on the right side a digraph with a (3,2)-Grundy function. 2 10 0 2 10 0 2 Figure 5. A digraph with a (2,2)-Grundy function and a digraph with a (3,2)-Grundy function. Remark 9. If a digraph Dhas a (k, l)-Grundy function g, then Dhas a (k, l)- kernel K={x∈V:g(x) = 0}. The number of Grundy functions of Dhas been proved to be equal to the number of Grundy functions of its line digraph, see [10]. Next, we extend this (k, l)-Kernels, Semikernels and Grundy Functions 863 result to (k, l)-Grundy functions and to partial line digraphs. First we prove that a digraph has a (k, l)-Grundy function if and only if any partial line digraph has a (k, l)-Grundy function. Lemma 10. Let l≥1and k≥2be two integers. Let Dbe a digraph with minimum in-degree at least 1having a (k, l)-Grundy function g. Let A′and φsatisfy the requirements of the definition of a partial line digraph, i.e., L(A′,φ)D=LD. Then gL:A′→Ndefined as gL(yx) = g(x)is a (k, l)-Grundy function on LD. Proof. Let g:V→Nbe a (k, l)-Grundy function on D= (V, A). Next, we prove that gL:A′→Nbe defined as gL(yx) = g(x) is a (k, l)-Grundy function on LD. Let yx ∈V(LD). First, suppose that gL(yx) = t > 0. Since gL(yx) = g(x) = t > 0, by (1) of Definition 3, it follows that for each j < t, there is w∈N+ l(x) with g(w) = j. Hence, there is a path (x, x1,...,xr=w) in D with r≤l, which produces a path (yx, φ(xx1),...,φ(xr−1xr)) in LDof length r, yielding that φ(xr−1w)∈N+ l(yx)⊂V(LD). Therefore for each j < t, there is φ(xr−1w)∈N+ l(yx)⊂V(LD) and gL(φ(xr−1w)) = g(w) = j. Thus, gLmeets requirement (1) of Definition 3. Now suppose that gL(yx) = t, so g(x) = t. Let uv ∈N+ k−1(yx)⊂V(LD), then there is a path (yx, φ(xx1),...,φ(xr−1xr) = uv) of length r≤k−1 in LD. Hence there is a path (x, x1,...,xr=v) in Dwith r≤k−1, yielding that g(v)6=tbecause v∈N+ k−1(x) applying (2) of Definition 3. Therefore for all uv ∈N+ k−1(yx), we have gL(uv) = gL(φ(xr−1xr)) = g(v)6=t. Thus, gLmeets requirement (2) of Definition 3, concluding that gLis a (k, l)- Grundy function on LD. Lemma 11. Let l≥1and k≥2be two integers such that l≤k−1. Let Dbe a digraph with minimum in-degree at least 1. Let A′and φsatisfy the requirements of the definition of a partial line digraph, i.e., L(A′,φ)D=LD. Suppose that gis a(k, l)-Grundy function on LD. Then gD:V→Ndefined as gD(x) = g(yx), yx ∈A′, is a (k, l)-Grundy function on D. Proof. Let g:A′→Nbe a (k, l)-Grundy function on LD. First, let us prove that gD:V→Ndefined as gD(x) = g(yx) with x∈Vand yx ∈A′is a function. So assume that there are two arcs yx, y′x∈A′, such that g(yx)6= g(y′x). Suppose 0 ≤h=g(yx)< g(y′x), then there exists uv ∈N+ l(y′x)⊂ V(LD) such that g(uv) = hby condition (1) of Definition 3. Then there is a path (y′x, φ(xx1), . . . , φ(xr−1xr) = uv) of length r≤lin LD, and also a path (yx, φ(xx1),...,φ(xr−1xr) = uv) of length r≤lin LDimplying that uv ∈ N+ l(yx)⊆N+ k−1(yx) because l≤k−1, and g(yx) = g(uv) = hwhich is a contradiction with (2) of Definition 3. Therefore g(yx) = g(y′x). Furthermore, for every x∈V, there is an arc yx ∈A′by definition of LD. Hence, gD(x) exists for all x∈V. Thus gDis a function.