ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 19 (2020) 61-76
https://doi.org/10.26493/1855-3974.2106.423
(Also available at http://amc-journal.eu)
Dominating sets in finite generalized quadrangles*
*
Tamas Héger t ©
MTA-ELTE Geometric and Algebraic Combinatorics Research Group, ELTE Eotvos Lorând University, Pazmany Péter sétâny 1/C, Budapest, Hungary, H-1117
A dominating set in a graph is a set of vertices such that each vertex not in the set has a neighbor in the set. The domination number is the smallest size of a dominating set. We consider this problem in the incidence graph of a generalized quadrangle. We show that the domination number of a generalized quadrangle with parameters s and t is at most 2 st + 1, and we prove that this bound is sharp if s = t or if s = q - 1 and t = q +1. Moreover, we give a complete classification of smallest dominating sets in generalized quadrangles where s = t, and give some general results for small dominating sets in the general case.
Keywords: Dominating set, finite generalized quadrangle. Math. Subj. Class. (2020): 05B25, 05C69, 51E12
1 Preliminaries
Dominating sets in graphs have already been studied in 1958, but there was a boost of interest after the publishing of a survey paper in the '70s by Cockayne and Hedetniemi [3], in which the authors show that the domination problem is related to the well-known problem of colorings of graphs. In [8] a dominating set is defined as follows:
*The authors gratefully acknowledge the support of the FWO-HAS mobility grant 'Substructures in finite projective spaces: algebraic and extremal questions'. The authors also wish to thank Jan De Beule and Leo Storme for the discussions during this work, and the anonymous referee for a clarifying comment.
t Supported by the Janos Bolyai Research Scholarship of the Hungarian Academy of Sciences and by NKFIH OTKA Grant No. K124950.
E-mail addresses: heger@caesar.elte.hu (Tamas Heger), lihernan@vub.be (Lisa Hernandez Lucas)
Lisa Hernandez Lucas ©
Department of Mathematics, Vrije Universiteit Brüssel, Pleinlaan 2, 1050 Brussels, Belgium
Received 30 August 2019, accepted 25 March 2020, published online 2 November 2020
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
18
Ars Math. Contemp. 19 (2020) 62-23
Definition 1.1. Let G = (V, E) be a graph. The closed neighborhood N [S] of a set of vertices S is defined as the set of vertices adjacent to any vertex in S, joint with the vertices of S itself. A set D C V is a dominating set if N [D] = V.
It is desirable to find the smallest dominating sets in a graph. The number of vertices in the smallest dominating set in a graph G is the domination number of G, and a common notation for it is r(G).
The problem of domination has been studied before in incidence graphs of geometric structures, see for instance [6] and [11]. Also, perfect dominating sets of the incidence graphs of finite generalized quadrangles were considered in [4] (see also [9]), and for the particular quadrangle Q(4, q), they were studied in detail in [2]; see Section 5 for further information. In this paper, we will consider dominating sets in the incidence graph of finite generalized quadrangles.
Generalized quadrangles were first introduced by Tits [14]. In [13], Payne and Thas give the following definition of finite generalized quadrangles:
Definition 1.2. A finite generalized quadrangle GQ(s, t) with parameters s and t, where s, t > 1, is a point-line incidence structure (P, B, I), in which P is the set of points, B is the set of lines and I is a symmetric point-line incidence relation, satisfying the following axioms:
•	Each point is incident with t +1 lines and two distinct points are incident with at most one line.
•	Each line is incident with s + 1 points and two distinct lines are incident with at most one point.
•	If x is a point and L is a line not incident with x, then there is a unique pair (y, M) G P x B for which x I M I y I L.
We will refer to this third property as the projection property. A generalized quadrangle GQ(s,t) with parameters s and t is said to have order (s,t). It is well known that the number of points in a generalized quadrangle of order (s,t) is (s +1)(st + 1), and the number of lines is (t + 1)(st + 1). For two points P and Q, we will write P ~ Q if there exists a line incident with both (that is, they are collinear), and we will use this notation dually for lines as well.
For readability, we will refer to a dominating set in the incidence graph of GQ(s, t) and the domination number of the incidence graph of GQ(s, t) as a dominating set in GQ(s, t) and the domination number of GQ(s, t).
When viewed from a geometric perspective, a dominating set in GQ(s, t) becomes the union of a set of points and a set of lines such that each point which is not in the set is incident with a line from the set and such that each line which is not in the set is incident with a point from the set. This is closely related to the concept of blocking sets and the dual concept of covers.
Definition 1.3. A blocking set in GQ(s, t) is a set of points such that each line is incident with at least one of these points. A cover in GQ(s, t) is a set of lines such that each point is incident with at least one of these lines.
A blocking set O such that no two points from O are collinear is called an ovoid, a cover S such that no two lines from S are concurrent is called a spread. An arbitrary set
T. Heger and L. H. Lucas: Dominating sets infinite generalized quadrangles	63
of points O such that no two points from the set are collinear is called a partial ovoid, an arbitrary set of lines S such that no two lines from S are concurrent is called a partial spread. Let us note that an ovoid or a spread in GQ(s, t) contains exactly st + 1 elements, and this is the smallest possibe size for a blocking set or a covering set.
In Section 2 we will show that there exist dominating sets in GQ(s, t) of size 2st + 1 and that the union of a blocking set and a cover exceeds this size. This motivates us to call a dominating set in GQ(s, t) small when it has size at most 2st + 1. This section also lists some properties of small dominating sets in GQ(s, t). In Section 3 we show that all small dominating sets in GQ(s, t), where |s - t| < 3 must have size 2st + 1, which shows that the domination number in this case is 2st + 1. In particular, this gives us the domination number of GQ(q, q) and GQ(q - 1, q + 1). In Section 4 we give a classification of small dominating sets in GQ(q, q). In Section 5 we give a summary of the main results, and add some open problems.
2 Examples and properties of small dominating sets in GQ(s, t)
Consider a generalized quadrangle GQ(s,t). We will construct a dominating set D of size 2st + 1 as follows. Let P be a point in GQ(s, t). Number the lines through P as ¿4, ¿2,..., ^i+i. Now define P as the set of all points which are incident with one of the first t lines ¿1,..., ¿t through P, including P itself. Then |P| = st + 1. Now define L as the set of lines which intersect the last line ¿i+1 in a point different from P. Then |L| = st. Define D = PU L. The construction is also shown in Figure 1.
The size of D is 2st + 1. Now take an arbitrary point Q in GQ(s, t). If Q is incident with li+1, then it is either contained in the dominating set (if Q = P), or covered by t different lines from the dominating set. So assume Q is not incident with ¿i+1. Then by the projection property of generalized quadrangles, there exists a unique point-line pair (R, m) such that R is incident with ¿i+1 and m is incident with both Q and R. If m is one of the lines l1,...,li, then Q is a point of the dominating set. Otherwise, m must be a line intersecting ¿i+1 in a point different from P. Then m is in the dominating set and Q is covered.
Now take an arbitrary line Assume I is not incident with P. Then again by the projection property of generalized quadrangles, there exists a unique point-line pair (R, m) such that R is incident with I and m is incident with both P and R. If R is incident with li+1, then I intersects ¿i+1 in a point different from P, so it must be one of the lines in the dominating set. Otherwise, R is incident with one of the lines l1,...,li, hence it is in the dominating set. In this case I is blocked.
So D is indeed a dominating set of GQ(s, t). We now have Theorem 2.1.
Theorem 2.1. For any finite generalized quadrangle GQ(s,t) there exists a dominating set of size 2st + 1.
Note that the construction in Theorem 2.1 can be dualized, giving us a second example of a dominating set of size 2st + 1. We can also get this dual structure by omitting the point P from the dominating set and adding the line ¿i+1 to it. See also Figure 1.
From a graph-theoretical point of view, we can get the dominating set from Theorem 2.1 or its dual as follows. Fix one edge {P, ¿} in the incidence graph, then all points with distance two from {P, ¿} together with {P} (resp. together with {¿}) form the dominating
18
Ars Math. Contemp. 19 (2020) 64-23
set from Theorem 2.1 (resp. its dual)1.
Let us note that this dominating set is a maximal independent set in the incidence graph. Maximal independent sets are clearly dominating sets; however, the converse is not always true. Even when the dominating set has the smallest size possible, it is not necessarily a independent set. Families of graphs for which the smallest dominating sets are independent also form a subject of study.
In the case of non-thick generalized quadrangles; that is, when s = 1 or t = 1, we immediately have the following result.
Theorem 2.2. The domination number of GQ(q, 1) and GQ(1, q) is 2q + 1; furthermore, dominating sets of size 2q +1 are independent.
Proof. By duality, it is sufficient to show this result for GQ(q, 1). The points and lines of GQ(q, 1) may naturally be viewed as the (q + 1)2 points together with the q +1 horizontal and q + 1 vertical lines of a (q +1) x (q + 1) grid.
Let D be a dominating set of size |D| < 2q+1, and let lv and lh stand for the number of vertical and horizontal lines in D, respectively. If lh = q +1, then for each vertical line we must have either the line or a point on the line in D, hence |D| > 2q + 2, a contradiction. Thus lh < q, and similarly lv < q.
If lh = q, then for all the q +1 points on the horizontal line not in D, D must contain either the point or the vertical line through it, whence |D| > 2q +1. Since we assumed |D| < 2q + 1, we now have |D| = 2q + 1. Moreover, note that D is independent in this case. A similar argument works for lv = q.
Suppose now lh < q - 1 and lv < q - 1. The lines of D leave exactly (q + 1 - lh)(q + 1 - lv) points not covered, which all must be in D, whence
(q + 1)2 - (lh + lv)(q + 1) + lhlv + (lh + lv) < |D| < 2q +1.
As lh < q -1 and lv < q -1, we have lv + lh < 2q - 2 and lhlv > (q - 1)(lh + lv - (q -1)), hence
2q +1 > (q +1)2 - (lh + lv)q + lhlv > (q + 1)2 - (lh + lv) - (q - 1)2 > 4q - (2q - 2),
1 The authors wish to thank Sam Mattheus (VUB) for this remark.
T. Heger and L. H. Lucas: Dominating sets infinite generalized quadrangles	65
a contradiction.
We can conclude that the size of a dominating set D is at least 2q + 1, and that D is independent in this case. Theorem 2.1 assures that such a dominating set indeed exists. □
From now on, we will assume that our generalized quadrangle is thick; that is, s > 2 and t > 2.
The most trivial dominating sets are the union of a blocking set and a cover. If an ovoid and a spread exist, then their union forms a dominating set of size 2st + 2. So by Theorem 2.1, the union of an ovoid and a spread is definitely not the smallest dominating set. Moreover, we can prove that any dominating set containing a blocking set or a cover exceeds the size 2st + 1.
Lemma 2.3. Let D = PD U LD be a dominating set in GQ(s,t), s,t > 2, with PD the points and LD the lines of D. If PD is a blocking set or LD is a cover, then |D| > 2st + 2. Moreover, if equality holds, then PD is an ovoid and LD is a spread.
Proof. Assume without loss of generality that PD is a blocking set. The case where LD is a cover can be showed analogously. Assume |D| < 2st + 2, then |Pd | < 2st + 2 - |Ld |. Any point that is not in PD needs to be covered at least once by a line of LD. But since PD is a blocking set, each line of LD contains at least one point of PD, meaning it can only cover at most s points not in PD. This gives us the following inequality:
(s + 1)(st + 1) < |PdI + s|Ld| < 2st + 2 - |LdI + s|Ld|,
whence (s - 1)(st + 1) < (s - 1)|Ld|, and thus st +1 < |Ld| follows. Since PD is a blocking set, we have that |Pd| > st +1. But then |D| = |P| + |L| > 2st + 2, so the lower bound on |D| is proved.
Assume now that equality holds. Then |Pd | = |Ld | = st + 1 and LD covers each point not in D exactly once. We want to show that LD covers each point of PD exactly once as well. As PD is a blocking set, its size implies it being an ovoid, so each line of Ld covers at most one point of PD. Suppose that there exists a point P G PD not covered by Ld. Then each of the (t + 1)s points collinear with P, which are not in PD, must be covered by a line of LD which, due to the projection property, are pairwise distinct, implying |Ld | > st + s > st + 1, a contradiction. Hence LD is a cover of size st + 1, that is, a spread.	□
Lemma 2.3, together with Theorem 2.1, motivates the following definition:
Definition 2.4. Let D be a dominating set in GQ(s, t). Then D is a small dominating set if | D | < 2st + 1.
The following two lemmas also provide us with some information regarding the size of a dominating set or, more precisely, regarding the size of the set of points and the set of lines contained in a dominating set.
Lemma 2.5. Let P be an arbitrary point set in GQ(s, t). Assume there exists a number A such that
VP GP: |{Q G P | Q = P,Q - P}| > A. Then the number of lines in GQ(s, t) not blocked by P is at least
(t+1)(st+1 -IPI)+.
18
Ars Math. Contemp. 19 (2020) 66-23
Proof. For any line i in GQ(s, t), define the degree d(i) of i as the number of points in P which are incident with i. Let Lb be the set of lines blocked by P. Then
|Lb| = |P|(t + 1) - E (d(i) - 1).	(2.1)
eecb
Now let X := {(P,Q) | P,Q € P,P = Q,P - Q}. Then we have the following inequalities:
|P|A < |X| = E d(i)(d(i) - 1) < (s + 1) E (d(i) - 1),
eeCb	ieCb
implying that < J2eecb (d(i) - 1). Together with (2.1) this yields:
|Lfo| < |p|(t+1) - spa.
Since the total number of lines in GQ(s, t) is (t + 1)(st +1) it follows that the number of lines not blocked by P is at least (t + 1)(st + 1 - |P|) + .	□
If P is the point set of a dominating set, then Lemma 2.5 gives a lower bound on the number of lines contained in this dominating set. By dualizing this lemma we find:
Lemma 2.6. Let L be an arbitrary line set in GQ(s, t). Assume there exists a number A such that
Vi € L: |{m € L | m = i, m - i}| > A. Then the number of points in GQ(s, t) not covered by the line set L is at least
|L|A
(s + 1)(st + 1 -|L|) +
t +1'
Notation 2.7. Let D be a dominating set in GQ(s, t). Let PD and LD denote the point set and the line set of D, resp. Define P' and L' as the set of points and the set of lines resp., that are not covered by LD and not blocked by PD resp. We will use this notation in the sequel implicitly. Note that by the definition of a dominating set, P' CPD and L' CLD.
The following Lemma allows us to apply Lemma 2.5.
Lemma 2.8. Let D be a dominating set in GQ(s, t). For any point in P', the number of points in P' collinear with it is at least Ap := st + s - |LD |. For any line in L' the number of lines in L' concurrent with it is at least AL := st +1 - |PD |.
Proof. Let P be an arbitrary point in P'. Then each line of D covers at most one point collinear with P. Hence, there are at least Ap := (t + 1)s - |LD| points collinear with P which are not covered by a line of D. These points must be in P'. So each point of P' is collinear with at least Ap other points of P'. Dually, we have that each line of L' is concurrent with at least AL := st +1 - |PD | other lines of L'.	□
From the next lemma follows that Ap and AL are non-negative.
T. Heger and L. H. Lucas: Dominating sets infinite generalized quadrangles	67
Lemma 2.9. Let D be a dominating set in GQ(s, t). If |D| < 2st + 1, then
st - s +1 < |PD |< st + t,	(2.2)
st - t +1 < |Ld|< st + s.	(2.3)
Proof. Assume |PD | = st +1 - e, then at least e(t +1) lines are not blocked by PD and have to be in LD. This implies that
2st + 1 > |D| = |Pd| + |Ld| > st + 1 - e + e(t + 1),
from which follows that e < s. Hence |PD |> st - s + 1. From this we obtain
2st +1 > |D| = |Pd| + |Ld| > st - s + 1 + |Ld|,
hence |LD | < st + s. The other two inequalities follow similarly.	□
3 The domination number of GQ(s,t), |s — t| small
Theorem 3.1. The domination number of GQ(s, t), where |s - t| < 3, is 2st + 1.
Proof. By Theorem 2.1, it is enough to show r(GQ(s, t)) > 2st+1. Assume a dominating set D exists with size smaller than 2st + 1. When lines or points are added to a dominating set, it still remains a dominating set, so without loss of generality we may assume that D has size |D| = 2st.
Let l = |Ld| andp = |PD|, and let Ap and AL be as in Lemma 2.8. By Lemma 2.5 we have that the number of lines not blocked by P' is at least (st+1 - |P '|)(t+1) + |Ps_+z1P. Since each point of D can block at most t + 1 lines, the number of lines |L'| not blocked by D is at least
|L'| > (st +1 - |P'|)(t + 1) + ^^ - (p - |P'|)(t + 1)
s+1
= (st +1 - P)(t + 1) + ^.
s+1
Dually, by Lemma 2.6, we find that
|P '|> (st + 1 - i)(s + 1) +	.
Suppose, say, l < p (we may consider the dual quadrangle otherwise). Let 0 < e < t be such thatp = st+e, l = st-e (cf. Lemma 2.9). Filling in these and Ap = st+s-1 = s+e and Al = st +1 - p = t - e, multiplying by s +1 and t + 1 resp., and rearranging we get
(s + 1)|L'| - (s + e)|P'| > (1 - e)(t + 1)(s + 1),	(3.1)
(t + 1)|P'| - (t - e)|L'| > (1 + e)(t + 1)(s + 1).	(3.2)
Suppose |P'| < |L'|. Then (3.2) yields
(1 + e)(t + 1)(s + 1) < (t +1)|P'|- (t -e)|L'| < (1 + e)|L'| < (1 + e)|£D| < (1 + e)st, a contradiction. Hence |P'| > |L'|. Then (3.1) gives
(1 - e)(t + 1)(s + 1) < (s + 1)|L'| - (s + e)|P'| < (1 - e)|P'| < (1 - e)(st + t),
18
68	Ars Math. Contemp. 19 (2020) 125-145
a contradiction if e < 1; thus e > 2. Adding up (3.1) and (3.2) we find
2(t+1)(s + 1) < (t - s - e + 1)|P'|-(t -s-e-1)|L'| = (t - s-e-1)(|P'| - |L'|) + 2|P'|.
As t - s < 3, e + 1 > 3, |P'| - |L'| > 0 and |P'| < |PD| < st +1, this is a contradiction. Consequently, |D| > 2st.	□
Corollary 3.2. The domination number of GQ(q, q) is 2q2 +1, and the domination number of GQ(q + 1, q - 1) and GQ(q - 1, q +1) is 2q2 - 1.
This corollary applies to the well-known quadrangles W(q), Q(4, q), T2(O) (these have order (q, q)), T2* (O) (of order (q - 1, q + 1), q even), AS(q) (of order (q - 1, q + 1), q odd) and their duals (of order (q + 1, q - 1)). Let us note that these quadrangles yield isomorphic incidence graphs in many cases. Clearly, the incidence graphs of a GQ and its dual are isomorphic. Let us now fix q. It is known that W (q) is isomorphic to the dual of Q(4, q), and that T2(O) is isomorphic to Q(4, q) if and only if the oval O is a conic [13, Section 3.2], which is certainly the case when q is odd by B. Segre's celebrated result. However, when q is even, O may be an oval that is not a conic, in which case the construction T2 (O) gives new instances of GQs of order (q, q) and corresponding incidence graphs. In case of order (q - 1, q + 1), q even, there are also examples of GQs other than T|(O) [13].
4 Classification of the smallest dominating sets in GQ(q, q)
Corollary 3.2 shows that all small dominating sets in GQ(q, q) have size 2q2 + 1. Moreover, we already have two constructions of small dominating sets, namely the construction from Theorem 2.1 and its dual. In this section we show that these are the only two small dominating sets.
First we need a few lemmas regarding the structure of small dominating sets in GQ(q, q).
Lemma 4.1. Let D = PD U LD be a dominating set in GQ(q, q) of size 2q2 + 1. Then P' is not a partial ovoid and L is not a partial spread.
Proof. It is sufficient to show that P' cannot be a partial ovoid. It then follows by duality that L' cannot be a spread. So assume to the contrary that P' is a partial ovoid, this will lead to a contradiction.
Take a point P G P'. Since P' is a partial ovoid, all points collinear with P are not in P'. So they need to be covered by at least q2 + q different lines from LD .By Lemma 2.9 we now have that |LD| = q2 + q and |PD| = q2 - q + 1 > |P'|.
Now let n be the number of lines that are blocked by points of PD \ P', but are not in L D and are not blocked by a point of P'. Then we can count the total number of lines in GQ(q,q):
q3 + q2 + q +1 = |Ld | + (q +1)|P '| + n
Note that n < (q2 - q +1 - |P'|)q, since each point of PD \ P' is covered at least once by Ld , so it contributes at most q lines to n. Remember that |LD | = q2 + q. We now find that:
q3 + q2 + q +1 < q2 + q + (q + 1)|P'| + (q2 - q +1 - |P'|)q,
which implies that |P'| > q2 - q +1. This means that P' = PD. So all points of the dominating set are uncovered.
T. Heger and L. H. Lucas: Dominating sets infinite generalized quadrangles	69
Since |Ld | > q2 + 1, the set of lines LD cannot form a partial spread, meaning some of these lines must intersect. Assume there exist three lines ¿^ ¿2, ¿3 G LD such that ¿1 intersects both ¿2 and ¿3, in different points. Each point Q G PD can be projected onto ¿1. The projection point needs to be different from the points where ¿2 and ¿3 intersect ¿1. Otherwise, there would not be enough lines in LD to cover all points collinear to Q. Different points from PD will have different projection lines, since no two points from PD are collinear. This implies that |Pd | < (q - 1)q = q2 - q, which is a contradiction. From this we can conclude that each line of LD must cover at least q points which are not covered by any other line of LD.
We can now start counting again:
q3 + q2 + q +1 > |Pd I + q|LD | = q2 - q + 1 + q(q2 + q) = q3 + 2q2 - q + 1,
from which q < 2 follows, yielding an obvious contradiction. Hence, P' cannot be a partial ovoid.	□
Note that since P' C PD, this lemma implies that PD cannot be a partial ovoid either and, dually, LD is not a partial spread.
The following two theorems give a characterization for the dominating set constructed in Theorem 2.1, and its dual.
Theorem 4.2. Let D = PD U LD be a dominating set in GQ(q, q) of size 2q2 + 1. Let the degree d^) of a line ¿ be the number of points of P' that are incident with ¿. If all lines in GQ(q, q) have d^) G {0,1, q +1}, then D is the dominating set from Theorem 2.1.
Proof. Suppose that every line ¿ of the GQ(q, q) admits «¿(¿) G {0,1, q + 1}. If there is no line with «¿(¿) = q +1, then P' is a partial ovoid, which is not possible according to Lemma 4.1. So there is at least one line with degree q +1. Then every point of P' must be contained in a line of degree at least two since either it is contained in a line of degree q +1 or it can be projected to one such line, and then the projection line has degree at least two. Since as soon as a line has degree at least two, it is completely contained in P' as a point set, this yields that P' can be obtained as the union of some lines.
Assume there are two non-intersecting lines ¿ and m contained (as a set of points) in P'. Then each point of ¿ can be projected onto m. All these projection lines have degree at least two, so they are contained in P' as well (as point sets). But then |Pd | > (q +1)2 > q2 + q, which contradicts Lemma 2.9.
Hence, P' is a set of k lines through a point P. Note that |P'| = kq +1, so by Lemma 2.9, 1 < k < q. There are q +1 - k lines through P that, aside from P itself, do not contain points of P'. So all points on these lines, except for P, must be covered. This leads to (q +1 - k)q lines from LD. These lines of L cover altogether at most (q +1 - k)q(q +1) points. The other lines of LD can cover at most q points that are not covered yet by these first lines. This leads to the following inequality:
q3 + q2 + q +1 < kq + 1 + (q +1 - k)q(q + 1) + (|LdI - (q + 1 - k)q) q
= kq + 1 + (q +1 - k)q2 + q2 + q - kq + |LD|q - (q +1 - k)q2 = q2 + q +1 + |Ld |q,
hence |Ld| > q2.
70
Ars Math. Contemp. 19 (2020) 125-145
The number of lines blocked by the elements of P' is kq2 + q +1. Consider a point Q in PD \ P'. This point needs to be covered at least once by a line of CD .By projecting this point on one of the k lines through P, we see that there is at least one line through Q that is already blocked by a point from P'. Hence, each point of PD \ P' can block at most q - 1 lines that are not in CD and are not blocked by a point of P'. So for the size of this set we obtain
m	q3 + q2 + q + 1 - |Ld |- (kq2 + q + 1) q3 + q2 - kq2 - |£p |
|Pd\p|--q--=-q--.
Using this inequality and the observation that |Cd | - q2, we find for the size of the dominating set D = (PD \ P') UP' U CD that
mNq3 + q2 - kq2 - |cd 1 , , , , lr ,
|D| - ----+ kq +1 + |LdI
q -1
= q3 + q2 - kq2 + kq +1+ f1 - ) |Ld I- q^^f + kq +1 + q2 q - 1	q - 1	q - 1
1k
= q2 + (1 - k)q + (1 - k) +-- + kq + 1 + q2
q -1
2 , k - 1
= 2q2 + q + 2 - k---.
q-1
Now assuming k < q, we find that |D| > 2q2 + 1, which is a contradiction. So the only possibility left is k = q. In this case P' consists of the points on q lines through P, and |P'| = q2 + 1. The number of lines blocked by these points is q3 + q +1. Since |Ld | - q2, all lines not blocked by the points of P' must be in CD. So D is the dominating set constructed in Theorem 2.1.	□
Dualizing this theorem gives us a characterization for the dual of the construction in Theorem 2.1.
Theorem 4.3. Let D = PD U CD be a dominating set in GQ(q, q) of size 2q2 + 1. Let the degree d(P) of a point P be the number of lines of C that are incident with P. If all points in GQ(q, q) have d(P) G {0,1, q + 1}, then D is the dual dominating set from Theorem 2.1.
We will need the following lemma, which is actually a variation on Lemma 2.5.
Lemma 4.4. Let D = PD U CD be a dominating set in GQ(q, q) of size 2q2 + 1. Let p := |Pd |, l := |Cd |, and define Ap = q2 + q - l and AL = q2 + q - p as in Lemma 2.8. Define the degree d(^) of a line t as the number of points from PD incident with £, and the degree d(P) of a point P as the number of lines from CD incident with P. Finally, we introduce
c(D) = ^ (q +1 - d(Q))(d(Q) - 1) + ^ (q +1 - d(t))(d(t) - 1)
Q/Vd
+ E d(P)+ E d(t).
PeVD	eeLD
T. Heger and L. H. Lucas: Dominating sets infinite generalized quadrangles	71
Then
p > (q2 + 1 - 1)(q + 1) + ^(1Al + c(D)) ,
q +1
l > (q2 + 1 - p)(q + 1) +--^r (pAp + c(D)) .
q +1
Proof: Let p' := |Pand l' := |L'|. Note that for a line t, d(t) > 1 iff t £ L'. With p(q + 1), we count each line t blocked by PD exactly d(t) times, hence the number of lines blocked by PD is
p(q + 1) - E (d(t) -1) - E (d(t) - 1)
i/Ld	i/Ld\L'
= p(q + 1) - E (d(t) - 1) - ( E d(t) - l + l'
I/LD	\eeCD
Recall that l' equals the number of lines not blocked by PD, hence l' = (q2 + 1)(q + 1) -(4.1). From this it follows that
l = (q2 + 1 - p)(q + 1) + E (d(t) - 1) + E d(t).	(4.2)
i/LD	ie LD
We will estimate the middle term using
(q + 1) E (d(t) - 1)= E d(t)(d(t) - 1)+ E (q +1 - d(t))(d(t) - 1). (4.3)
1/ Ld	1/ Ld	1/Ld
Note that the second sum on the right-hand side is a part of c(D). For the sum
/ Ld d(t)(d(t) - 1) we can find a lower bound as follows.
For P G PD, let N'(P) denote the number of points of P' collinear with P. Then
E d(t)(d(t) - 1) = |{(P, Q, t): t £ Ld, P G Pd, Q G Pd, P - Q, PQ = t}| i/LD	> |{(P,Q,t): t £ Ld ,P gPd ,Q gP',P - Q,PQ = t}|
= |{(P,Q): P gPd ,Q G P', P - Q}| = E N' (P).
P/PD
Let P G PD. Then we have
l > d(P)+ E d(Q)=d(P)+ E d(Q)
Q-P	Q-P
PQ / LD	Q/P'
PQ / Ld
= d(P) + (q + 1 - d(P))q - N'(P)+ E (d(Q) - 1),
Q-P Q /P' PQ / Ld
whence
N'(P) > Ap - (q - 1)d(P)+ E (d(Q) - 1).
Q-P
Q /P'
PQ / Ld
72
Ars Math. Contemp. 19 (2020) 125-145
With this we find
£ N'(P) > pAp - (q - 1) £ d(P)+ £ £ (d(Q) - 1)
peVD	peVD	PePd q-p
q ev
PQ / LD
> pAp - (q - 1) £ d(P) + £ £ (d(Q) - 1)
p e Pd	PePd Q-p
Q / Pd PQ / LD
= pAp - (q - 1) £ d(P)+ £ £ (d(Q) - 1).
P ePd	Q ePD P ePd
Q-P PQ e Ld
As for each point Q G PD, there are q + 1 - d(Q) lines on Q that are not in LD and each of these must be incident with a point of PD, we find that
£ N'(P) > pAp - (q - 1) £ d(P) + £ (q +1 - d(Q))(d(Q) - 1).
P ePD	P ePD	Q / Pd
As E* eLd dW = Ep ePD d(P^ we conclude
£ d(*)(d(*) - 1) > pAP - (q - 1) £ d(*) + £ (q + 1 - d(Q))(d(Q) - 1).
^e Ld	ee LD	Q e Pd
Together with (4.2) and (4.3), this gives the second desired inequality. The other inequality is showed analogously.	□
Note that P' = PD and L' = LD are equivalent. Also note that if this is the case, then Ee eLd d(^) = 0. We can now prove the following Theorem, giving a classification of the small dominating sets in GQ(q, q).
Theorem 4.5. Let D = PD U LD be a dominating set in GQ(q, q) with size |D | = 2q2 +1. Then D is the dominating set from Theorem 2.1 or its dual.
Proof. Definep = |Pd|, l = |Ld| andp' = |P'|; note thatp + l = 2q2 + 1. By duality, we may assume that p > l + 1 or p = q2 (and l = q2 + 1). Define the degree d(^) of a line I as the number of points from PD incident with and the degree d(P) of a point P as the number of lines from L D incident with P. We will find lower bounds on the sums from Lemma 4.4; let c(D) be defined as therein.
Define A := Ap = q2 + q - l as in Lemma 2.8. For any point P G PD, define the number of neighbors N(P) := |{Q | Q ~ P, Q G PD}|. We immediately have that N(P) > A if P G P'. If l = q2 + 1, then A = q -1. If p > l + 1,then q2 - q +1 < l < q2, by Lemma 2.9. In both cases, we have that A ^ 0 (mod q). We now consider two types of points in P' and their contributions to c(D).
• Type 1: P is incident with at least one line e with 2 < d(e) < q.
Since P is a point from P', the line e is not in LD. So this line e contributes at least q - 1 to eld (q +1 - d(^)) (d(^) - 1). Note that on this line there are at most
T. Heger and L. H. Lucas: Dominating sets infinite generalized quadrangles	73
q points of Type 1. Assume there are k points of Type 1, then we find the following lower bound:
£ (q +1 - d(*)) (d(^) - 1) > k^-1.	(4.4)
e^Ln	q
• Type 2: All lines through P have degree 1 or q + 1 .
If A = N(P), then there are exactly A points in PD collinear with P. But A ^ 0 (mod q), so then there must be at least one line I through P with degree 2 < d(^) < q. Then P would be a point of Type 1. So we have N(P) > A.
Denote by x» (P) := |{R | R G Pd ,R - P, d(R) = i}|, for i = 1,...,q. Note that, as P G P' there are no points collinear with P with degree q + 1.
Each point R G PD, with degree 1 < i < q contributes (q +1 - i)(i - 1) to the sum ^Q&Vd (q + 1 - d(Q)) (d(Q) - 1). Such a point is collinear with at most q + 1 - i points of Type 2, since a line through a point of Type 2 is not in LD, and either contains no other points of PD or contains only points of PD. So the contribution of
P to £WVd (q +1 - d(Q)) (d(Q) - 1) is at least
« (q +1 - i)(i - 1) *
—q+r-i— = 2. x»(i -1). »=1 h »=i
Now we show that the contribution is strictly positive for each point of Type 2. So assume this is not the case for a point P G P' of Type 2, so each point Q G PD collinear with P has degree d(Q) = 1. Since each line through P has either degree 1 or q +1, there must be A lines through P which contain all points collinear with it from P, for some 1 < A < q +1 (A> 0 as N(P) > 0). So we already have Aq +1 points in the dominating set.
On each of the other q + 1 - A lines through P there are q points with degree 1. This gives us q(q +1 - A) lines in the dominating set. Through each of these points G PD, collinear with P there are q - 1 lines which are not in the dominating set and are not blocked yet. Say there are x points in D, which are not collinear with P and different from P itself. Each of these points can block at most q + 1 - A lines which are not yet blocked. From this follows (q - 1)q(q +1 - A) < x(q +1 - A), hence x > q2 - q. Since 2q2 + 1 = |D| > Aq + 1 + x + (q +1 - A)q = q2 + q + 1 + x, we have x = q2 - q. As q2 + q > |PD | = x + Aq + 1 = q2 + (A - 1)q + 1, we have A =1 and |PD | = q2 + 1, contrary to our assumptions.
From this follows that we may assume that for each point P of Type 2 we have J2i=1 x»(i - 1) > 1. Note that there are p' - k points of Type 2. This gives us the following inequality:
£ (q +1 - d(Q)) (d(Q) - 1) > p' - k.	(4.5)
Qi-Vn
Note that d(P) > 1 for each P G PD \ P', s^^ d(^) = £p v d(P) > p - p'.
74
Ars Math. Contemp. 19 (2020) 125-145
Combining this with (4.4) and (4.5), and with k < p' < p andp > q2, we get the following:
c(D) = £ (q +1 - d(*))(d(*) - 1)
+ £ (q +1 - d(Q))(d(Q) - 1) + 2 £ d(P)
Q0Vo	PeVo
> kq—1 + p' - k + 2(p - p') > kq—1 + p - k qq
k q -1 2
> p--> p- > q - q.
qq
Thus, according to Lemma 4.4, we find
p > (q2 + 1 - 1)(q + 1) + (/A, + q2 - q) ,
q +1
/ > (q2 + 1 - p)(q + 1) + —^r (pAp + q2 - q) .
q +1
Now using 2q2 + 1 = |D| = p + /, Ap = q2 + q - /, AL = q2 + q - p, and that p/ < q2(q2 + 1), we calculate the sum of these two inequalities:
2q2 + 1 > q + 1 + p(q2 + q - /) + /(q2 + q - p) + 2(q2 - q)
= q + 1 +
q+1
(p + /)q(q +1) - 2p/ + 2(q2 - q)
q +1
, 2 , -2p/ + 2(q2 - q) q +1 + q(2q2 + 1) + p + -q)
q +1
-2q4 - 2q2 + 2q2 - 2q
> 2q3 + 2q + 1 +
> 2q3 + 2q + 1 - 2q
q +1
q3 + 1
q +1
> 2q3 + 2q + 1 - 2q(q2 - q + 1) = 2q2 + 1.
So we see that we actually reach equality. This means that all the estimates we used during our countings were exact, hence we have k = p' = p. As PD = P', every point P G PD has d(P) = 0. Equality with zero in (4.5) yields that for all Q G PD we have d(Q) = 1 or d(Q) = q +1. By Theorem 4.3, D is the dual of the dominating set from Theorem 2.1. □
5 Conclusion, remarks and open problems
The main results of this paper can be summarized as follows. Theorem 5.1.
•	The domination number of GQ(s, t) is at most 2st + 1.
•	The domination number of GQ(q, q) equals 2q2 + 1.
•	A dominating set of GQ(q, q) of size 2q + 1 is one of the two examples seen in Figure 1.
T. Heger and L. H. Lucas: Dominating sets infinite generalized quadrangles	75
• The domination number of GQ(q — 1, q +1) and GQ(q + 1, q — 1) equals 2q2 — 1.
Let us outline some possible areas of further investigation in this topic. For the other classical parameters, the calculations in Lemma 3.1 fail in general. Is the bound 2st + 1 for GQ(s,t) still sharp for general s and t? It would be also interesting to answer this question for the classical generalized quadrangles. We have checked by computer, using a simple linear integer programming model and Gurobi [7], for all classical GQs of order (3,9), (4, 8), (4,16) as given on Moorhouse's webpage [12], and we have found the bound sharp.
In W(q), or Q(4, q), if q is even, there exists an ovoid and a spread as well, giving rise to a dominating set of size 2q2 + 2. This implies that there is no general stability phenomenon for smallest dominating sets in GQs, unlike in the case of generalized triangles (projective planes; see [11]); that is, the size of minimal examples (with respect to containment) may be arbitrarily close. However, the structure of the mentioned dominating sets are immensely dissimilar. Is it true that minimal dominating sets of size 2q2 + 2 of a GQ(q, q) (or, more specifically, W(q)) are the union of an ovoid and a spread? What size does the next smallest minimal example for a dominating set in GQ(q, q) have?
Dominating sets of a graph G = (V, E) may be also viewed as a set D of vertices such that V \ D induces a subgraph of G such that every vertex has degree at least one smaller than originally. If equality holds for every vertex of V \ D, then D is called a perfect dominating set. More generally, if we replace 'at least one smaller' by 'at least t smaller', we talk about t-fold dominating sets and perfect t-fold dominating sets. Perfect t fold dominating sets of the incidence graphs of projective planes, generalized quadrangles and generalized hexagons have already been studied in order to produce upper bounds on the order of some particular cage graphs (see [9] for an overview). In [5], perfect t-fold dominating sets of the incidence graph of the desarguesian projective plane PG(2, q) are completely described for small enough t, while the characterization of small dominating sets of projective planes can be found in [ ]. In the case t = 1, describing smallest dominating and perfect dominating sets is quite easy, unlike in the here discussed case of generalized quadrangles; see also [2] for results on perfect (1-fold) dominating sets of Q(4, q). It would be also interesting to study t-fold (ordinary and perfect) dominating sets of generalized quadrangles, t > 2. Also, as a counterpart of t-fold dominating sets, finding a (preferably large) subset D of the incidence graph such that each vertex not in D has at most t neighbors in D would be also interesting, as its complement induces a subgraph of high minimum degree. Such subsets, asides being interesting in themselves, also may find their applications in different topics as they do when the host graph is the incidence graph of a projective plane; see [1, 10].
ORCID iDs
Tamas Heger t> https://orcid.org/0000-0002-9586-966X Lisa Hernandez Lucas © https://orcid.org/0000-0002-1356-5970
References
[1]	G. Araujo-Pardo and C. Balbuena, Constructions of small regular bipartite graphs of girth 6, Networks 57 (2011), 121-127, doi:10.1002/net.20392.
[2]	L. Beukemann and K. Metsch, Regular graphs constructed from the classical generalized quadrangle Q(4, q), J. Combin. Des. 19 (2011), 70-83, doi:10.1002/jcd.20266.
76
Ars Math. Contemp. 19 (2020) 125-145
[3]	E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), 247-261, doi:10.1002/net.3230070305.
[4]	A. Gacs and T. Heger, On geometric constructions of (k, g)-graphs, Contrib. Discrete Math. 3 (2008), 63-80, doi:10.11575/cdm.v3i1.61998.
[5]	A. Gacs, T. Heger and Zs. Weiner, On regular graphs of girth six arising from projective planes, European J. Combin. 34 (2013), 285-296, doi:10.1016/j.ejc.2012.07.005.
[6]	F. Goldberg, D. Rajendraprasad and R. Mathew, Domination in designs, arXiv:1405.3436 [math.CO] .
[7]	Gurobi Optimization, LLC, Gurobi Optimizer (Version 8.1), 2020, https://www. gurobi.com.
[8]	S. T. Hedetniemi and R. C. Laskar, Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math. 86 (1990), 257-277, doi:10.1016/ 0012-365x(90)90365-o.
[9]	T. Heger, Some graph theoretic aspects of finite geometries, Ph.D. thesis, ELTE Eotvos Lorand University, 2013.
[10]	T. Heger and S. Mattheus, Bipartite Ramsey numbers for the four-cycle versus stars emerging from projective planes, 2020, manuscript.
[11]	T. Heger and Z. L. Nagy, Dominating sets in projective planes, J. Combin. Des. 25 (2017), 293-309, doi:10.1002/jcd.21527.
[12]	E. Moorhouse, Generalised Polygons of Small Order, 2003, http://ericmoorhouse. org/pub/genpoly/.
[13]	S. E. Payne and J. A. Thas, Finite Generalized Quadrangles, EMS Series of Lectures in Mathematics, European Mathematical Society (EMS), Zurich, 2nd edition, 2009, doi:10.4171/066.
[14]	J. Tits, Sur la trialite et certains groupes qui s'en deduisent, Inst. Hautes 1Etudes Sci. Publ. Math. 2 (1959), 13-60, http://www.numdam.org/item?id=PMIHES_195 9_2_13_0.