/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 419-430 https://doi.org/10.26493/1855-3974.1881.384
(Also available at http://amc-journal.eu)
Grundy domination and zero forcing in Kneser
graphs*
Boštjan Brešar t
Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Tim Kos *
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Pablo Daniel Torres §
Depto. de Matemática, Universidad Nacional de Rosario and Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina
Received 17 December 2018, accepted 20 May 2019, published online 6 November 2019
Abstract
In this paper, we continue the investigation of different types of (Grundy) dominating sequences. We consider four different types of Grundy domination numbers and the related zero forcing numbers, focusing on these numbers in the well-known class of Kneser graphs Kn,r. In particular, we establish that the Grundy total domination number Ygr (Kn,r) equals (2rr) for any r > 2 and n > 2r +1. For the Grundy domination number of Kneser graphs we get Ygr (Knr) = a(Knr) whenever n is sufficiently larger than r. On the other hand, the zero forcing number Z(Kn,r) is proved to be (n) - (2rr) when n > 3r + 1 and r > 2, while lower and upper bounds are provided for Z(Kn,r) when 2r + 1 < n < 3r. Some lower bounds for different types of minimum ranks of Kneser graphs are also obtained along the way.
Keywords: Grundy domination number, Grundy total domination number, Kneser graph, zero forcing
number, minimum rank.
Math. Subj. Class.: 05C69, 05C76, 05D05
*This work was supported in part by the bilateral project MINCYT-MHEST SLO 1409.
t Supported by the Slovenian Research Agency (research core funding No. P1-0297 and the project grant No. J1-9109).
i Supported by the Slovenian Research Agency (research core funding No. P1-0297).
§ Author thanks the financial support from PICT 2016-0410 and PID-UNR ING 538-539. He also thanks University of Maribor for the financial support and hospitality.
E-mail addresses: bostjan.bresar@um.si (Boštjan Brešar), timkos89@gmail.com (Tim Kos), ptorres@fceia.unr.edu.ar (Pablo Daniel Torres)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
420
Ars Math. Contemp. 17 (2019) 349-368
1 Introduction
The Kneser graph, Kn,r, where n, r are positive integers such that n > 2r, has the r-subsets of the n-set as its vertices, and two r-subsets are adjacent in Kn,r if they are disjoint. The class of graphs became well-known by the celebrated Erdos-Ko-Rado theorem [11], which determined the independence number a(Knr) of the Kneser graph Kn r to be equal to (n. Another famous result is Lovasz's proof of Kneser's conjecture, which determines the chromatic number of Kneser graphs [22], see also Matousek for a combinatorial proof of this result [23]. Many other invariants were later considered in Kneser graphs by a number of authors. In particular, the domination number of Kneser graphs was studied in several papers [16, 19, 24], but there is no such complete solution for domination number of Kneser graphs as is the case with the chromatic and the independence number.
Various Grundy domination invariants have been introduced in recent years [5, 7, 8], arising from two standard domination invariants, the domination number and the total domination number. In the context of domination, we say that a vertex x totally dominates vertices in its (open) neighborhood, N(x) = {y | xy e E(G)}, and that x dominates vertices in its closed neigborhood, N[x] = N(x) U {x}. A set D in a graph G is a dominating set (resp., a total dominating set) of G if every vertex in V(G) is dominated (resp., totally dominated) by a vertex in D. (Clearly, G must not have an isolated vertex to have a total dominating set.) The minimum cardinality of a dominating set (resp., total dominating set) is the domination number (resp., the total domination number) of G, and is denoted by Y(G) (resp., 7t(G)). Now, Grundy (total) domination number is introduced while applying a greedy algorithm to obtain a (total) dominating set D as follows. Vertices are added to the set D one by one, requiring that a vertex x that was added to D (totally) dominates at least one vertex that was not (totally) dominated before this vertex was added. The longest length of such a sequence in a graph G is the Grundy (total) domination number, Ygr (G) (resp., Ygr (G)). By imposing an additional condition on such dominating sequences, one gets the so-called Z-dominating sequences and Z-Grundy domination number [4], denoted by yZ (G). See Section 2 for formal definitions, and [6, 9] for more results on Grundy domination and Grundy total domination numbers.
In [5] a strong connection between the Z-Grundy domination number and the zero forcing number of a graph was established. The latter graph invariant has been intensively studied in recent years; it is closely related to another well-known domination concept called power domination, cf. [13, 14]. Moreover, the zero forcing number is very useful in determining the minimum rank of a graph; see the seminal paper about this connection [1] and some further studies [2, 3, 10]. Minimum rank mr(G) of a graph G is defined as the minimum rank over all symmetric matrices that have non-zero (real) values in the non-zero entries of the adjacency matrix A(G) of G, arbitrary real values in the diagonal, and zero values in all other entries. (See the survey on minimum rank, where many applications and other interesting results on this parameter can be found [12].) In addition, the skew zero forcing number (denoted by Z_(G)) was introduced in [18], and studied in the context of the invariant mr0, which is a version of the minimum rank in which matrices are in addition required to have empty diagonals. Motivated by the results of [5], Lin [20] noticed a similar connection between the Grundy total domination number and the skew zero forcing number of graphs, and also between the Grundy domination number and another version of the minimum rank parameter, denoted by mr^. As shown by Lin [20], the following bounds hold:
Ygr(G) < mr,(G),	(G) < mro(G), YgZ(G) < mr(G).
B. Bresar et al.: Grundy domination and zero forcing in Kneser graphs
421
Consequently, any lower bound on a Grundy domination parameter gives a lower bound on the corresponding minimum rank parameter.
In this paper, we study four types of Grundy domination parameters (beside the mentioned ones also the L-Grundy domination number) in Kneser graphs, and apply the obtained results to give some bounds or exact results about zero forcing parameters and minimum rank parameters in Kneser graphs. In the next section, we give all the necessary definitions, establish the notation and present some preliminary results. In Section 3 we prove that Ygr(Kn,2) = a(Kn,2) = n - 1 for n > 6, while Ygr(K5,2) = 5. More generally, for Kneser graphs Kn,r when r > 2 we establish an asymptotic result, which states that there exists an n0 G N dependent on r such that for all n, n > n0, we have Ygr(Kn,r) = a(Kn,r) = . The most complete result is obtained for the Grundy total domination number, where we show that for r > 2 and n > 2r + 1, Ygr (Kn,r) = (20. This result is proven in Section 4, using a set theoretic result due to Gyarfas and Hubenko [15], which is the ordered version of Lovasz's result for set-pair collections [21]. Section 5 is about Z-Grundy domination number of Kneser graphs. We prove that for any r > 2 and n > 3r + 1, we have yZ (Kn,r) = (2rr). This immediately implies the result for Kneser grapht with r > 2 and n > 3r +1 about their zero forcing number, notably Z(Kn r) = - (2rr); and a lower bound for the minimum rank, which reads as mr(K„,r) > (2rr). On the other hand, when 2r + 1 < n < 3r and r > 2 we only prove the lower bound for Z-Grundy domination number: yZ (Kn,r) > (2rr) - (4r—i-n), which is dependent on both r and n. In Section 6, we investigate the L-Grundy domination number of Kneser graphs Kn r, provide the exact result when r = 2, and when r is bigger than 2 we prove a lower and an upper bound, which are not far apart. Finally, in the concluding section, we rephrase the Z-Grundy domination number and the Grundy domination number as set-theoretic problems.
2 Preliminaries and notation
Let [n] = {1,2,..., n}, where n G N. In [7] the first type of Grundy dominating sequences was introduced.
Let S = (vi,..., vk) be a sequence of distinct vertices of a graph G. The corresponding set {vi,..., vk} of vertices from the sequence S will be denoted by ¡3. The initial segment (vi,..., vj) of S will be denoted by Sj. Given a sequence S' = (ui,..., um) of vertices in G such that S n S' = 0, S © S' is the concatenation of S and S', i.e., S © S' = (vi,..., vk, ui,..., um). A sequence S = (vi,..., vk), where Vj G V(G), is called a closed neighborhood sequence if, for each i
j-i
N[vj] \ J N[vj] = 0.	(2.1)
If for a closed neighborhood sequence S, the set S3 is a dominating set of G, then S is called a dominating sequence of G. We will say that vj footprints the vertices from N[vj] \ ji N[vj], and that vj is the footprinter of any u G N[vj] \ U j=i N[vj]. For a dominating
sequence S, any vertex in V(G) has a unique footprinter in S. Clearly, the length k of a dominating sequence S = (vi,..., vk) is bounded from below by the domination number Y (G) of a graph G. We call the maximum length of a dominating sequence in G the Grundy
422
Ars Math. Contemp. 17 (2019) 349-368
domination number of a graph G and denote it by Ygr (G). The corresponding sequence is called a Grundy dominating sequence of G or Ygr -sequence of G.
In a similar way total dominating sequences were introduced in [8], when G is a graph without isolated vertices. Using the same notation as in the previous paragraph, we say that a sequence S = (vi;..., vk), where vi g V (G), is called an open neighborhood sequence if, for each i
i-i
N(vi) \ J N(vj) = 0.	(2.2)
j=i
We also speak of total footprinters of which meaning should be clear. It is easy to see that an open neighborhood sequence S in G of maximum length yields S to be a total dominating set; the sequence S is then called a Grundy total dominating sequence or ygr -sequence, and the corresponding invariant the Grundy total domination number of G, denoted Yfgr (G). Any open neighborhood sequence S, where S is a total dominating set is called a total dominating sequence.
Two additional variants of the Grundy (total) domination number were introduced in [5]. Let G be a graph without isolated vertices. A sequence S = (vi;..., vk), where vi g V(G), is called a Z-sequence if, for each i
i-i
N(vi) \ J N[vj] = 0.	(2.3)
j=i
Then the Z-Grundy domination number yZ (G) of the graph G is the length of a longest Z-sequence. Note that such a sequence is also a closed neighborhood sequence and hence yZ (G) < Ygr (G). Given a Z-sequence S, the corresponding set S of vertices will be called a Z-set. Note that yfr(G) = Ygr (G) if and only if there exists a Grundy dominating sequence for G each vertex of which footprints some of its neighbors.
mrL
mr i
Igr
Y
Z
Figure 1: Connections between different Grundy domination and minimum rank parameters.
B. Bresar et al.: Grundy domination and zero forcing in Kneser graphs
423
While observing the defining conditions of the three concepts in (2.1), (2.2) and (2.3), it is natural to consider also the fourth concept. It gives the longest sequences among all four versions, and we call it L-Grundy domination. Given a graph G, a sequence S = (vi,..., vk), where vi are distinct vertices from G, is called an L-sequence if, for each i
i-1
N[vi] \ U N(vj) = 0.	(2.4)
j=i
Then the L-Grundy domination number j^r (G) of the graph G is the length of a longest L-sequence. Given an L-sequence S, the corresponding set S of vertices will be called an L-set (the requirement that all vertices in S are distinct, indeed makes S to be a set, and prevents the creation of an infinite sequence by repetition of one and the same vertex). Note that it is possible that vi L-footprints only itself. We will make use of the following result.
Proposition 2.1 ([5, Proposition 3.1]). If G is a graph with no isolated vertices, then
(i)	YZr (G) < Ygr(G) < 7gr (G) - 1,
(ii)	yZ (G) < Ygr(G) < Ygr(G)
and all the bounds are sharp.
As mentioned earlier, Lin established the connections between different Grundy domination numbers, zero forcing numbers and minimum rank invariants. (For definitions of different zero forcing and minimum rank parameters we refer to [20].)
Theorem 2.2 ([20]). If G is a graph without isolated vertices, then
(1)	\V (G)|	- Z£(G)	= Ygr(G) < mr,(G),
(2)	|V (G)|	- Z-(G)	= Ygr (G) < mro(G)
(3)	\V (G)|	- Z(G) =	= Ygr(G) < mr(G).
(4)	\V (G)|	- Zl(G)	= Ygr (G) < mrL(G)
The connections between different Grundy domination and minimum rank parameters that follow from Proposition 2.1 and Theorem 2.2 are presented in the Hasse diagram in Figure 1.
3 Grundy domination number
It is easy to check (we did this by computer) that the Grundy domination number of the Petersen graph, K5,2, equals 5. Since this is bigger (by 1) than the independence number of the Petersen graph, it is somewhat surprising that for all n bigger than 5, the Grundy domination number equals the independence number of Kn,2.
Proposition 3.1. For n > 6, Ygr (Kn,2) = «(K„j2) = n - 1.
424
Ars Math. Contemp. 17 (2019) 349-368
Proof. Clearly, as a sequence of vertices forming a maximum independent set is a Grundy dominating sequence, we have Ygr(Kn,2) > a(Kn,2) = n - 1. In addition, we have checked by computer small cases, establishing Ygr (Kn,2) = n - 1, for 6 < n < 8.
For the proof of the reversed inequality for n > 8, let S = (vi,..., vk) be a Grundy dominating sequence of Suppose k > n - 1. Hence, S is not a stable set. We may assume that Si is a stable set for some i > 1, while vi+1 is adjacent to some vj e Si. Note that, since n > 6, we may assume without loss of generality that vj = {1, j + 1} for 1 < j < i (if i = 3 and Sj = {{1,2}, {1,3}, {2,3}}, then all vertices are already dominated by S^ a contradiction).
First, if i < 2, then after S3 = (v1, v2, v3), or S2 = (v1, v2) if i = 1, at most four vertices remain undominated, notably vertices from {{1, 3}, {1,4}, {2, 3}, {2,4}}. Hence, counting the largest possible number of steps, we get k < 7. As n > 8, this is only possible when n = 8, in which case we have Ygr (Kg,2) = 7, already noticed above.
Hence, we may assume that i > 2. Therefore, after the segment Si is included, only the vertices in {{1, i + 2},..., {1, n}} remain undominated. Since each vertex in the sequence S has to dominate some undominated vertex k < i + n - (i + 1) = n - 1, a contradiction.	□
While we could not find exact values of Grundy domination number for all Kneser graphs Kn,r, we prove in some sense similar result as we have for Kn,2. Namely, as soon as n is large enough with respect to a given r (e.g., when r = 2, this was n > 6), we can prove that Ygr (Kn,r) = a(Kn,r).
Theorem 3.2. For any r > 2, there exists n0 e N such that for all n, n > no, we have
n1
Ygr (Kn,r) = a(Kn r) . .
r - 1
Proof. The result is proven for r = 2 by Proposition 3.1. Fix r > 3, and consider a dominating sequence S = (v1,..., vm) of Kn r, assuming that S is not a stable set.
In the first case, suppose that already v1 and v2 are adjacent, and without loss of generality we may assume that v1 = {1,..., r} and v2 = {r + 1,..., 2r}. Let V' be the set of vertices, not dominated by {v1, v2}. Note that every element in V' is an r-set that contains at least one element from v1 and at least one element from v2. Denoting by c = {2r +1,..., n}, any element in V' consists of i elements from c, where 0 < i < r - 2, j elements from v1 , where 1 < j < r - i - 1, and consequently, r - i - j elements from v2 (note that r - i - j > 1 ).
Hence
IV '1 = g(" - 2r) feXr - r - i
Note that	1 (j) C-'j-J is not dependent on n, hence for fixed r this is a constant,
while J2r=0 (n=j2r) is a polynomial in n of degree r - 2. Hence | V' | = O(nr=2). On the other hand, a(Kn,r) = (n=1), hence the resulting dominating sequence is of size Q(nr-1). Note that the length of the sequence S is at most 2 + | V'|. Hence, if n is big enough, S is
n
1
not a Grundy dominating sequence, because its length is less than r 1 .
In the second case, the initial segment of S, Sk, is a stable set, for some k > 1, while vfc+1 is adjacent to some vertex in Sk. Without loss of generality, we may assume that
B. Bresar et al.: Grundy domination and zero forcing in Kneser graphs
425
vk = {1,..., r} and vfc+1 = {r + 1,..., 2r}. Note as above that the size of the set V' of vertices in Kn,r, which are not in N(vk) U N(vk+1) is O(nr-2). To complete the proof of this case, consider the subgraph G' = Kn r - (UveSfc N[v]). Note that G' must have an edge, for otherwise the proof is already done (indeed, no edges in this graph means, that an optimal sequence S consists of the stable set Sk U V(G')). Let ab be an edge in V(G'). Clearly, for all vertices v in Sk, v is not adjacent to the endvertices of ab, i.e., we have v n a = 0 and v n b = 0. In the same way as above we get that the longest such sequence Sfc has at most £r-02 (n-2r) E^-i-1 (j)(r-rj-i) vertices, and so |Sfc | = k is of the order O(nr-2). Note that the set of vertices not footprinted by vertices in Sk+1 is contained in V'. Then |Sk+1| + |V'| = k + 1 + |V'| is an upper bound for |S| and remains of the order O(nr-2). Therefore, for n big enough, |S| will not be greater that (n-1), which is of order Q(nr-1).	□
For the zero forcing parameter Z^ and minimum rank parameter mr^ Theorem 3.2 gives the following observation.
Corollary 3.3. For any r > 2, there exists n0 G N such that for all n, n > n0, we have
Note that for 2r +1 < n < n0 a lower bound could be improved by improving the values of ygr(Kn,r). It would be even more interesting to find an upper bound for mr<j(K„,r), which might require tools from linear algebra.
Unfortunately, we do not know how large must be n0 in Theorem 3.2 and Corollary 3.3 when r > 3. This is an interesting issue yet to be investigated. We could only check by computer that Ygr (K7 3) = 20, while clearly a(K7 3) = 15.
4 Grundy total domination number
Unlike the Grundy domination number, we prove that the Grundy total domination number of Kn,r does not depend on n. Moreover, we provide the exact value of jfgr (Kn,r) for all cases. To this end, we use an ordered version of Lovasz's result for set-pair collections [21] provided by Gyarfas and Hubenko [15].
Lemma 4.1 ([15, Lemma 1]). Let T = {(Ai, Bi) | 1 < i < k} be a set-pair collection with |Ai| = a, ^^ = b satisfying the following conditions:
1.	Ai n Bi = 0 for 1 < i < k;
2.	Ai n Bj = 0 for 1 < i < j < k. Then k < (°+6).
Proposition 4.2. For r > 2 and n > 2r +1, (K„,r) = (2rr).
Proof. In order to obtain the lower bound, it is enough to note that any sequence S such that S = {A c [2r] | |A| = r} is a total dominating sequence of Kn r.
and
426
Ars Math. Contemp. 17 (2019) 349-368
To prove the upper bound, let S = (vi,..., ) be a total dominating sequence of Kn,r. For 1 < i < k, let w be a vertex totally footprinted by vj. It is not hard to see that the set-pair collection T = {(vj, Wj) | 1 < i < k} satisfies both conditions in Lemma 4.1. Since |vj| = |uj| = r for 1 < i < k, then k < (2rr) and the result follows.	□
For the skew zero forcing number (G) and the minimum rank parameter mr0(G) we get the following consequences.
Corollary 4.3. If r > 2,n > 2r + 1, then Z_(K„,r) = ) - (2rr) and mro(K„,r) > (2rr). 5 Z-Grundy domination number
It is easy to check that the Z-Grundy domination number of the Petersen graph K5 2 and of K6,2 equal to 5. Note that Proposition 4.2 provided a general upper bound, i.e., for r > 2 and n > 2r + 1, yZ (Kn,r ) < (2rr). We can prove that this bound is reached in the following cases.
Proposition 5.1. For r > 2 and n > 3r +1, yZ* (K„,r ) = (2rr). Proof. Let us consider the following sets
51	= {A | A C [2r], 1 G A, |A| = r},
52	= {A | A C {r + 2, r + 3,..., 3r}, |A| = r} - {2r + 1,..., 3r}.
Let Si be any sequence of Si and let S2 be any sequence of S2. We claim that S = Si © ({2r + 1,..., 3r}) ©S2 is aZ-dominating sequence. Indeed, each u G Si Z-footprints at least f = [2r] - u, {2r + 1,..., 3r} Z-footprints [r - 1] U {3r + 1} and each v G S2 Z-footprints at least f = {1} U ()r + 2, r + 3,..., 3r} - v). Hence, yZ(Kn,r ) > |S| = |Si| + 1 + |S2| = 2(27i) = (2rr).	'
As we have mentioned, the equality follows directly from Proposition 2.1 and 4.2. □
Proposition 5.2. For r > 2 and 2r +1 < n < 3r, yJT (K„,r ) > (2rr) - (^i;").
Proof. Let us consider the following sets
51	= {A | A C [2r], 1 G A, |A| = r},
52	= {A | A C {n - 2r + 2, n - 2r + 3,..., n}, {2r + 1,..., n} C A, |A| = r}. Note, that
'2r - 1\ /2r - 1 - (n - 2r)\ /2r - 1\ /4r - 1 - n^
— — —
I 2I 1	1 1 r — (n — 2r) J \ r J ^ 3r — n
Let Si be any sequence of Si and let S2 be any sequence of S2. We claim that S = Si © S2 is a Z-dominating sequence. Indeed, each u g Si Z-footprints at least f = [2r] — u and each v g S2 Z-footprints at least f = {1} U ({n — 2r + 2, n — 2r + 3,..., n} — v). Hence, yZ) > |S| = |Si| + |S21 = 2-V) — -V;") = -2;) — ft;1;-).	□
Perhaps the most interesting case is that of odd graphs K(2r + 1, r):
B. Bresar et al.: Grundy domination and zero forcing in Kneser graphs
427
Corollary 5.3. For r > 2, (K2r+1,r) > (2;) - ft-"2) = ^-H2;-2).
For the zero forcing numbers of Kneser graphs we get the following. Corollary 5.4.
(i)	For r > 2 and 2r + 1 < n < 3r, Z(Kn,r) < (nr) - (2rr) + (4r3;1;n).
(ii)	For r > 2 and n > 3r +1, Z(Kn,r) = (, - (2rr).
Propositions 5.1 and 5.2 yield the following consequences for the minimum ranks,
mr(Kn,r).
Corollary 5.5.
(i)	For r > 2 and 2r + 1 < n < 3r, mr(Kn,r) > (2rr) - (4r3;1nn).
(ii)	For r > 2 and n > 3r +1, mr(Kn,r) > (2rr).
6 L-Grundy domination number
Proposition 6.1. For n > 5, 7^,(Kn,2) = n + 2.
Proof. First, we prove that S = ({1,2}, {1,3}, {1,4},..., {1, n}, {2,3}, {2,4}, {3,4}) is aL-sequence of Kn,2, where n > 5. Note that S is an L-sequence, since each {1, i}, where i € [n] - {1}, L-footprints itself, {2, 3} L-footprints {1,4}, {2,4} L-footprints {1,3}, and {3,4} L-footprints {1, 2}. Hence, (Kn,2) > n + 2.
For the proof of the reversed inequality for n > 5, let S = (v1,..., ) be a maximal L-sequence of Kn,2. We may assume without loss of generality that v1 = {1,2}. Clearly, v1 L-footprints itself and vertices of the form {i, j}, where i, j € [n] - {1, 2} and i = j. Next, assume v2 is a neighbor of v1. Without loss of generality we may assume v2 = {3,4}. Thus, v2 L-footprints itself and vertices of the form {i, j}, where i € {1,2}, j € [n] - {3,4} and i = j. Hence, just the vertices {1,3}, {1,4}, {2,3} and {2,4} remain not L-dominated by S2. The rest can be L-dominated with at most 4 vertices. Follows, |S| < 6 < n + 2.
Next, suppose v2 is not a neighbor of v1. Without loss of generality let v2 = {1,3}. In this case, the vertex {2,3} and the vertices of the form {1, i}, where i € [n] - {1}, remain not L-dominated by S2. Next, we distinguish again 4 cases:
(i)	v3 is a neighbor of v1 and v2 (v3 is of the form {i, j}, where i, j € [n] - {1,2,3} and i = j),
(ii)	v3 is a neighbor of v1 and not of v2 (v3 is of the form {3,i},where i € [n]-{1, 2,3}),
(iii)	v3 is a neighbor of v2 and not of v 1 (v3 is of the form { 2, i}, where i € [n] -{1, 2,3}), and
(iv)	v3 is not a neighbor of v1 or v2 (v3 is {2,3} or is of the form {1, i}, where i €
[n] -{1, 2, 3}).
In the cases (i), (ii), (iii) or if v3 = {2, 3} in the case (iv), there are at most 3 vertices left, that are not L-dominated by S3. In all cases we can L-dominate the rest with at most 4 vertices. Hence, |S| < 7 < n + 2.
428
Ars Math. Contemp. 17 (2019) 349-368
In the case (iv), where v3 = {1, i} (i G [n] - {1, 2, 3}), the vertex v3 L-footprints just itself and {2,3}. Hence, just the vertices of the form {1, i}, where i G [n] - {1}, remain not L-dominated by S3. Note, that it is possible that v, is first L-footprinted by itself and then later again by another vertex from S. Next, if v4 = {1,4}, then v4 just L-footprints itself and the same vertices stay not L-dominated. Hence, to make the sequence S as large as possible, next in the sequence can be vertices vj_i = {1, i} for i = 4,..., n.
Without loss of generality let vn = {2,3} (until now in the sequence are all vertices that contain 1). Hence, just the vertices {1,2} and {1,3} remain not L-dominated by Sn. Follows, |S| < n + 2.	□
Proposition 6.2. For r > 2 and n > 2r +1, (K„,r) > (^-1) + (2rr-1).
Proof. Let Si = {A | A c [n], 1 G A, |A| = r} and let S2 = {A | A c [2r] - {1}, |A| = r}. Let S1 be any sequence of S1 and let S2 be any sequence of S2. We claim that S = S1 © S2 is an L-dominating sequence.
Indeed, each u g S1 L-footprints at least itself and each v g S2 L-footprints at least
f = [2r] - v. Hence, yL(Kn,r) > |S| = |S1| + |S2| = (n_1) + (V).	□
For the upper bound, we first present a general result bounding the L-Grundy domination number of a graph G with no isolated vertices by using the independence number a(G) and the Grundy total domination number Ygr (G).
Proposition 6.3. For a graph G with no isolated vertices, yJT (G) < a(G) + (G) - 1.
Proof. Let S = (v1,..., vk) be an L-sequence of G. Let A, B and C be the sets of vertices of S such that every vertex in A only L-footprints itself, every vertex in B L-footprints itself and (at least) one more vertex and every vertex in C does not L-footprint itself. Note that {A, B, C} is a partition of S. Besides, A U B is a stable set of G. Hence, |A| + |B| < a(G). Let S' = (w1,..., wm) be the subsequence of S (respecting the order in S) such that S' = B U C. Clearly, S' is an open neighborhood sequence in G, thus m < 7gr(G).
Therefore, |S| = |A| + |B| + |C| < a(G)+ 7gr(G) -|B| < a(G)+ 7gr(G) - 1, since v1 G B.	□
Corollary 6.4. For r > 2 and n > 2r + 1, (Kn,r) < (n_1) + (2rr) - 1.
Note that the gap between the lower and the upper bound in Proposition 6.2 and Corollary 6.4 is (2r_^ - 1, which is fixed with respect to n.
7 Set-theoretic connections
Following the set-theoretic connections as in the case of Grundy total domination number (see Lemma 4.1), we ask the following.
Problem 7.1. Let T = {(A,, B,) | (A, U B,) C [n], |A,| = |B,| = r, for all i G [k]} be a set-pair collection satisfying the following conditions:
1.	A, n Bj = 0 or A, = Bj for 1 < i < k;
2.	A, n Bj = 0 and A, = B^ for 1 < i < j < k.
B. Bresar et al.: Grundy domination and zero forcing in Kneser graphs
429
Note that |T| = k.
Determine the smallest value f (n, r) for which k < f (n, r) for all such set-pair collections T.
From Theorem 3.2, for any r > 2 there exists n0 e N such that for all n, n > no, we have f (n, r) = Ygr (Kn,r) = a(Kn,r) = . Note that in this case, the cardinality n of the universal set in which A» and B» are contained plays an important role in determining f (n, r). As we see in the next case, allowing condition A» = B» is also relevant to the problem.
In a similar way, we propose the corresponding question for the Z-Grundy domination number.
Problem 7.2. Let T = {(A*, B») | (A U B») C [n], |A»| = |B»| = r, for all i e [k]} be a set-pair collection satisfying the following conditions:
1.	A* n B» = 0 for 1 < i < k;
2.	A» n Bj = 0 and A* = B^ for 1 < i < j < k. Note that |T| = k.
Determine the smallest value fZ (n, r) for which k < fZ (n, r) for all such set-pair collections T.
Note that fZ(n, r) = (Kn,r) = (2rr) for n > 3r +1. In this case fZ(n, r) is independent of n, but it is unclear whether this function is dependent on n when 2r +1 <
n < 3r.
References
[1]	AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), 1628-1648, doi:10.1016/j.laa.2007.10.009.
[2]	F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, Zero forcing parameters and minimum rank problems, Linear Algebra Appl. 433 (2010), 401-411, doi:10.1016/j.laa.2010.03.008.
[3]	F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory 72 (2013), 146-177, doi:10.1002/jgt.21637.
[4]	B. Bresar, Cs. Bujtas, T. Gologranc, S. KlavZar, G. Kosmrlj, B. Patkds, Zs. Tuza and M. Vizer, Dominating sequences in grid-like and toroidal graphs, Electron. J. Combin. 23 (2016), #P4.34 (19 pages), https://www.combinatorics.org/ojs/index.php/eljc/ article/view/v2 3i4p34.
[5]	B. Bresar, Cs. Bujtas, T. Gologranc, S. KlavZar, G. Kosmrlj, B. Patkds, Zs. Tuza and M. Vizer, Grundy dominating sequences and zero forcing sets, Discrete Optim. 26 (2017), 66-77, doi: 10.1016/j.disopt.2017.07.001.
[6]	B. Bresar, T. Gologranc and T. Kos, Dominating sequences under atomic changes with applications in Sierpinski and interval graphs, Appl. Anal. Discrete Math. 10 (2016), 518-531, doi:10.2298/aadm161005024b.
[7]	B. Bresar, T. Gologranc, M. Milanic, D. F. Rall and R. Rizzi, Dominating sequences in graphs, Discrete Math. 336 (2014), 22-36, doi:10.1016/j.disc.2014.07.016.
430
Ars Math. Contemp. 17 (2019) 349-368
[8]	B. Bresar, M. A. Henning and D. F. Rail, Total dominating sequences in graphs, Discrete Math. 339 (2016), 1665-1676, doi:10.1016/j.disc.2016.01.017.
[9]	B. Bresar, T. Kos, G. Nasini and P. Torres, Total dominating sequences in trees, split graphs, and under modular decomposition, Discrete Optim. 28 (2018), 16-30, doi:10.1016/j.disopt. 2017.10.002.
[10]	C. J. Edholm, L. Hogben, M. Huynh, J. LaGrange and D. D. Row, Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph, Linear Algebra Appl. 436 (2012), 4352-4372, doi:10.1016/j.laa.2010.10.015.
[11]	P. Erdos, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. 12 (1961), 313-320, doi:10.1093/qmath/12.1.313.
[12]	S. M. Fallat and L. Hogben, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl. 426 (2007), 558-582, doi:10.1016/j.laa.2007.05.036.
[13]	D. Ferrero, L. Hogben, F. H. J. Kenter and M. Young, The relationship between k-forcing and k-power domination, Discrete Math. 341 (2018), 1789-1797, doi:10.1016/j.disc.2017.10.031.
[14]	M. Gentner and D. Rautenbach, Some bounds on the zero forcing number of a graph, Discrete Appl. Math. 236 (2018), 203-213, doi:10.1016/j.dam.2017.11.015.
[15]	A. Gyarfas and A. Hubenko, Semistrong edge coloring of graphs, J. Graph Theory 49 (2005), 39-47, doi:10.1002/jgt.20061.
[16]	C. Hartman and D. B. West, Covering designs and domination in Kneser graphs, 2003, unpublished manuscript.
[17]	A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. 18 (1967), 369-384, doi:10.1093/qmath/18.1.369.
[18]	IMA-ISU research group on minimum rank, Minimum rank of skew-symmetric matrices described by a graph, Linear Algebra Appl. 432 (2010), 2457-2472, doi:10.1016/j.laa.2009.10. 001.
[19]	J. Ivanco and B. Zelinka, Domination in Kneser graphs, Math. Bohem. 118 (1993), 147-152, https://dml.cz/handle/10 338.dmlcz/12 6050.
[20]	J. C.-H. Lin, Zero forcing number, Grundy domination number, and their variants, Linear Algebra Appl. 563 (2019), 240-254, doi:10.1016/j.laa.2018.11.003.
[21]	L. Lovasz, Flats in matroids and geometric graphs, in: P. J. Cameron (ed.), Combinatorial Surveys, Academic Press, New York, 1977 pp. 45-86, proceedings of the Sixth British Combinatorial Conference held at the Royal Holloway College, Egham, July, 1977.
[22]	L. Lovasz, Kneser's conjecture, chromatic number, and homotopy, J. Comb. Theory Ser. A 25 (1978), 319-324, doi:10.1016/0097-3165(78)90022-5.
[23]	J. Matousek, A combinatorial proof of Kneser's conjecture, Combinatorica 24 (2004), 163170, doi:10.1007/s00493-004-0011-1.
[24]	P. R. J. Ostergard, Z. Shao and X. Xu, Bounds on the domination number of Kneser graphs, ArsMath. Contemp. 9 (2015), 187-195, doi:10.26493/1855-3974.491.b02.