ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.05
https://doi.org/10.26493/1855-3974.2771.4df
(Also available at http://amc-journal.eu)
Optimal strategies in fractional games:
vertex cover and domination
Csilla Bujtás *
Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia and
University of Pannonia, Veszprém, Hungary and
Institute of Mathematics, Physics and Mechanics, Jadranska 19, Ljubljana, Slovenia
Günter Rote
Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, Germany
Zsolt Tuza †
HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda u. 13–15,
1053 Budapest, Hungary and
Department of Computer Science and Systems Technology, University of Pannonia,
Egyetem u. 10, 8200 Veszprém, Hungary
Received 14 December 2021, accepted 27 February 2024, published online 18 July 2024
Abstract
In a hypergraph H = (V, E) with vertex set V and edge set E , a real-valued function
f : V → [0, 1] is a fractional transversal if
∑
v∈E f(v) ≥ 1 holds for every E ∈ E . Its
size is |f | :=
∑
v∈V f(v), and the fractional transversal number τ
∗(H) is the smallest
possible |f |.
We consider a game scenario where two players have opposite goals, one of them trying
to minimize and the other to maximize the size of a fractional transversal constructed in-
crementally. We prove that both players have strategies to achieve their common optimum,
and they can reach their goals using rational weights.
Keywords: Fractional vertex cover, fractional transversal game, fractional domination game.
Math. Subj. Class. (2020): 05C69, 05C65, 05C57
*Corresponding author. The author acknowledges the financial support from the Slovenian Research and
Innovation Agency under the projects N1-0108 and P1-0297.
†The author’s research was supported in part by the National Research, Development and Innovation Office –
NKFIH under the grant SNN 129364.
E-mail addresses: bujtasc@gmail.com (Csilla Bujtás), rote@inf.fu-berlin.de (Günter Rote),
tuza@dcs.uni-pannon.hu (Zsolt Tuza)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P3.05
1 Introduction
Let H = (V, E) be a finite hypergraph, where V is the finite vertex set and E is the edge
set, a set system over the underlying set V . We assume that every edge contains at least
one vertex; that is, E ⊆ 2V \ {∅}. A hypergraph is k-uniform if |E| = k holds for all
E ∈ E . A set T ⊆ V is a transversal 1 of H if every edge is covered by a vertex of T ,
which formally means that T ∩ E ̸= ∅ holds for all E ∈ E . Its real relaxation, called
fractional transversal, is a function f : V → [0, 1] such that
∑
v∈E f(v) ≥ 1 holds for
every E ∈ E . The size of f is defined as |f | :=
∑
v∈V f(v). The transversal number
τ(H) and the fractional transversal number τ∗(H) of H are the minimum cardinality |T |
of a transversal and minimum value |f | of a fractional transversal, respectively.
The transversal game is a competitive optimization version of hypergraph transversals,
which was introduced in [9] and studied further in [10]. It is played on a hypergraph H by
two players called Edge-hitter and Staller. They take turns choosing a vertex. The game
is over when all edges are covered, and the length of the game is the number of vertices
chosen by the players until the end of the game. Edge-hitter wants to finish the game as
soon as possible, while Staller wants to delay the end. To prevent Staller from making
completely useless moves, we stipulate that the chosen vertex must be contained in at least
one previously uncovered edge.
Assuming that both players play optimally2 and Edge-hitter starts, the length of the
game on H is uniquely determined. It is called the game transversal number of H and is
denoted by τg(H). Analogously, the Staller-start game transversal number of H, denoted
by τ ′g(H), is the length of the game under the same rules when Staller makes the first
move. Among other results, it was proved in [9] that |τg(H) − τ ′g(H)| ≤ 1 always holds.
We further recall that, denoting by n(H) and m(H) the number of vertices and edges in H
respectively, 411 (n(H) +m(H)) is a (sharp) upper bound on τg(H) if H does not contain
one-element edges and it is not isomorphic to the cycle C4.
Below we shall refer to this game as the integer game, as opposed to its fractional
version which we will introduce in the next section.
The important motivation of this approach are the domination game [7] and the to-
tal domination game [17], where in fact the transversal game is played on the ‘closed
neighborhood hypergraph’ and on the ‘open neighborhood hypergraph’ of a graph, re-
spectively.3 Further variants studied so far include the disjoint domination [14], con-
nected domination [2], and fractional domination [15] games on graphs, and the dom-
ination games on hypergraphs [13]. Some of the most recent results can be found in
[3, 4, 8, 11, 12, 16, 18, 19, 20, 21, 22, 23]. For a thorough survey and list of further
1In various areas of discrete mathematics and computer science, a transversal is called vertex cover, or hitting
set, or blocking set. It is also equivalent to the set cover in the dual hypergraph.
2A strategy of a player means that every possible state of the game is associated with a move he/she will play
if that situation arises. From Edge-hitter’s point of view, the value vE(S) of a strategy S is the smallest integer
k such that, if Edge-hitter plays according to S, the transversal game always finishes in at most k moves (no
matter which strategy is applied by Staller). We say that S is an optimal strategy for Edge-hitter, if vE(S) is
the possible smallest value over the family of all strategies. Similarly, from Staller’s point of view, a strategy S
can be associated with the value vS(S) that is the largest integer k such that, if Staller follows strategy S, the
length of the game is always at least k; further S is an optimal strategy for Staller, if vS(S) is the largest value
over the family of all strategies. The reader may find more about optimal strategies and the uniqueness of the
corresponding parameters in [5, Section 1.2].
3Recall from the literature that the closed and open neighborhood hypergraphs of a graph G are defined on the
same vertex set V as G, and the closed (resp. open) neighborhood hypergraph consists of edges corresponding to
the closed (resp. open) neighborhoods of vertices in G.
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 3
references see the book [5].
Our results
In Section 2 we introduce the rules of the game and prove that its value is well-defined. We
present some examples, showing that it makes a difference whether Edge-hitter or Staller
starts. Moreover, edges that are supersets of other edges of the hypergraph may influence
the game value, in contrast to the standard non-game version of the transversal number.
In Section 3 we compare the game transversal number with other related parameters,
and prove a monotonicity property, implying that changing the starting player can affect
the value of the game by at most 1.
The rules of the game allow the players to split their moves into infinitely many sub-
moves. In Section 4 and 5 we give some structural results showing that the full generality
of the moves allowed by our rules is not needed. Namely, any infinite move is equivalent to
a finite move, and Edge-hitter can restrict his strategy to moves in which every permutation
of submoves is equally good.
In Section 6 we prove that the game can be modeled in a way that leads to an opti-
mization problem solvable via the theory of piecewise linear continuous rational functions.
From this, we derive that the game value is rational for every finite hypergraph; moreover
both players can achieve their goals using rational submoves.
Consequences concerning domination games and several conjectures are given in the
concluding Section 7.
2 Fractional transversal game
Let H = (V, E) be a hypergraph. In the context of the fractional transversal game, we will
consider a cover function t : V → [0, 1] that is updated after each move during the game.
We denote by |t| the sum
∑
v∈V t(v). Given a cover function t, the corresponding load
function is ℓ : E → [0, 1] defined by the rule
ℓ(E) = ℓ(E, t) = min
{
1,
∑
v∈E
t(v)
}
for every E ∈ E . If ℓ ≡ 1, we say that H is fully covered. We shall write ti and ℓi for the
cover and load functions after the ith move.
The game begins with t0 ≡ 0 and therefore with ℓ0 ≡ 0. It is finished when the
hypergraph becomes fully covered. Edge-hitter and Staller take turns making moves under
the following rules. As long as ℓ ̸≡ 1, the next player performs a move, which is a sequence
(vi1 , w1), (vi2 , w2), . . . of arbitrary length (possibly infinite). It consists of the submoves
(vik , wk), k = 1, 2, . . . , where vi1 , vi2 , . . . are vertices of H with any number of repetitions
allowed, and the weights w1, w2, . . . are real numbers from [0, 1].
We say that a submove (vik , wk) is legal if it increases the load of some edge by wk. In
a legal move, a player makes a series of legal submoves such that the sum of the weights
equals 1 or the move completes the game, whichever comes first. Formally, the ith move
(vi1 , w1), (vi2 , w2), . . . is legal, if the following conditions hold:
(∗) For every k ≥ 1 there exists an edge E ∈ E such that vik ∈ E and
ℓi−1(E) +
( ∑
vis
∈E
1≤s≤k−1
ws
)
+ wk ≤ 1 .
4 Ars Math. Contemp. 24 (2024) #P3.05
(∗∗) The total weight constraint:
∑
k≥1 wk ≤ 1, and if the move does not end the game,
then
∑
k≥1 wk = 1.
The cover function ti can gradually be reached from ti−1 by adding the weight wk to
t(vik) after each submove; this process converts also the corresponding load function from
ℓi−1 to ℓi.
Suppose that a fractional transversal game G finishes with the qth move. The value |G|
of the game is defined as the value |tq| of the cover function obtained at the end, that is
the sum of the weights that have been spent during the game. The goal of Edge-hitter is to
achieve a value |G| as small as possible, while Staller wants a large |G|.
Assuming that Edge-hitter starts the fractional transversal game on H, we consider the
set of upper bounds,
UH = {a ∈ R : Edge-hitter has a strategy that ensures |G| ≤ a}
and the set of lower bounds,
LH = {b ∈ R : Staller has a strategy that ensures |G| ≥ b}.
Formally the game fractional transversal number τ∗g (H) is defined as
τ∗g (H) = inf(UH).
The Staller-start game fractional transversal number τ∗g
′(H) is defined similarly, under the
condition that the first move is made by Staller.
The following assertion shows that τ∗g (H) is also equal to sup(LH), and the situation is
similar if Staller starts the game. The proof is essentially the same as the one for the game
fractional domination number in [15].
Proposition 2.1. For every hypergraph H we have inf(UH) = sup(LH), and the analo-
gous equality holds for the Staller-start game, too.
Proof. First, assume that inf(UH) < sup(LH) and consequently, there exist two reals x
and y satisfying inf(UH) < x < y < sup(LH). By definition, x ∈ UH and, therefore,
Edge-hitter can ensure that, under every strategy of Staller, the value of the game is at most
x. Similarly, y ∈ LH and Staller has a strategy that ensures |G| ≥ y whatever strategy is
followed by Edge-hitter. This is a contradiction that establishes inf(UH) ≥ sup(LH).
Now, we prove the reverse inequality. By definition, z < inf(UH) implies that Edge-
hitter does not have a strategy to achieve |G| ≤ z. That is, against each strategy of Edge-
hitter there is a strategy of Staller which results in |G| > z. We may infer that z ∈ LH and
therefore z ≤ sup(LH). Since it holds for every z < inf(UH), we conclude inf(UH) ≤
sup(LH). This completes the proof of the proposition.
Later, in Section 6, we will show that inf(UH) = min(UH) and sup(LH) = max(LH).
Therefore, Edge-hitter and Staller have optimal strategies under which, respectively, |G| ≤
τ∗g (H) and |G| ≥ τ∗g (H) are achieved.
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 5
2.1 Examples for the fractional transversal game
(1) Our first example is the 4-cycle C4 = v1v2v3v4v1, which can also be considered
as a 2-uniform hypergraph. It is easy to check that τ∗(C4) = 2, while τg(C4) = 3 and
τ ′g(C4) = 2 were proved for the integer games [9]. Now we prove that τ
∗
g (C4) = 5/2.
• For the upper bound, the following strategy of Edge-hitter ensures that the sum of
the weights spent during the game is at most 5/2. His first move is (v1, 14 ), (v2,
1
4 ),
(v3,
1
4 ), (v4,
1
4 ); it results in ℓ1 ≡
1
2 and
∑
E∈E ℓ1(E) = 2. Then, for the first
1
2
of the weight spent by Staller, each of her submoves necessarily increases the load
of both incident edges; and each of her remaining submoves increases the load of
at least one edge. Therefore, the total load increases by at least 12 × 2 +
1
2 =
3
2 to∑
E∈E ℓ2(E) ≥
7
2 , and Edge-hitter can achieve
∑
E∈E ℓ3(E) = 4 by spending at
most 12 in the final move. This proves τ
∗
g (C4) ≤ 5/2.
• Let us show the reverse inequality. We note that the first move of the game has the
same effect as a sequence (v1, w1), (v2, w2), (v3, w3), (v4, w4) of submoves with∑4
i=1 wi = 1.
4 After this move of Edge-hitter,
∑
E∈E ℓ1(E) = 2 and hence, there
is an edge E with ℓ1(E) ≤ 12 . By symmetry, we may assume that ℓ1(v1v2) ≤
1
2 . Let
Staller play the move (v3, w1+w4), (v4, w2+w3). The move is legal as ℓ1(v2v3) =
w2 + w3 = 1 − (w1 + w4) and ℓ1(v4v1) = w1 + w4 = 1 − (w2 + w3). We then
have ℓ2(v1v2) = ℓ1(v1v2) ≤ 12 and Edge-hitter needs to spend at least
1
2 to finish the
game. This strategy of Staller shows τ∗g (C4) ≥ 5/2.
If Staller starts the fractional transversal game on C4 with the move (v1, w1), (v2, w2),
(v3, w3), (v4, w4), then Edge-hitter can ensure |G| = 2 by playing (v1, w3), (v2, w4),
(v3, w1), (v4, w2). Indeed, ℓ2 assigns w1 +w2 +w3 +w4 = 1 to every edge of the graph.
Therefore, τ∗g
′(C4) ≤ 2. Since τ∗g
′(C4) ≥ τ∗(C4) = 2 also holds5, we get τ∗g
′(C4) = 2.
v4
u4
v1
u1
v2
u2
v3
u3
Figure 1: A hypergraph H with nested edges.
4Theorem 4.1 and Lemma 5.1 will give conditions for this replacement property in general. For the first move
of the game, it is much easier to see as, for each edge E, its load ℓ1(E) equals the sum of the weights assigned to
the vertices of E.
5See the proof of Proposition 3.1(i) for a simple explanation.
6 Ars Math. Contemp. 24 (2024) #P3.05
(2) Now we modify the previous example C4 by adding four new vertices u1, . . . , u4 and
four new edges {v1, v2, u1}, . . . , {v4, v1, u4} to get the hypergraph H shown in Figure 1.
When the fractional (or integer) transversal number is considered, each edge that is a super-
set of another edge can be deleted, which implies τ∗(H) = τ∗(C4) = 2. We show that the
situation is different for the fractional transversal game on H, that is τ∗g (H) = 3 ̸= τ∗g (C4).
Suppose that Edge-hitter starts the fractional transversal game G on H.
• We first show that Edge-hitter can ensure that the value |G| of the game is at most
3. An optimal first move for him is (v1, 14 ), (v2,
1
4 ), (v3,
1
4 ), (v4,
1
4 ). Then, inde-
pendently of Staller’s reply, Edge-hitter plays (v1, w1), (v2, w2), (v3, w3), (v4, w4)
as his second move, where wi equals 14 or, if (vi,
1
4 ) is not a legal submove, wi is
the maximum legal weight for vi. After this move, ℓ3 ≡ 1 and we may infer that
|G| ≤ 3. This proves τ∗g (H) ≤ 3.
• Our second claim is that Staller has a strategy that always results in |G| ≥ 3. As
each vertex of H belongs to at most two 3-element edges, after Edge-hitter’s first
move the sum of the loads of the 3-element edges is at most 2. Thus, Staller can
play a legal move that does not assign weights to v1, v2, v3, v4. After this move, the
sum of the loads of the 2-element edges remains at most 2, and Edge-hitter has to
spend a weight of at least 1 to finish the game. This shows τ∗g (H) ≥ 3. We therefore
conclude τ∗g (H) = 3 > τ∗g (C4).
(3) The removal of the edges which are subsets of other edges in a hypergraph F may
also change the values of the parameters. For instance, let F be the hypergraph obtained
from C4 by adding the 4-element edge E = {v1, v2, v3, v4}. As the load of E equals 1
after the first move in the game, it is easy to see that τ∗g (F) = τ∗g (C4) = 5/2, while the
removal of all 2-element edges results in a one-edge hypergraph F ′ with τ∗g (F ′) = 1.
3 Some basic facts and the Continuation Principle
In this section we first observe some simple inequalities which are analogous to the ones in
other games concerning graph domination and hypergraph transversal, most notably to the
fractional domination game [15].
Proposition 3.1.
(i) For every hypergraph H, it holds that
τ∗(H) ≤ τ∗g (H) < 2τ∗(H) and τ∗(H) ≤ τ∗g
′(H) < 2τ∗(H) + 1.
(ii) There is no universal constant C with τg(H) ≤ C · τ∗g (H), and not even with
τ(H) ≤ C · τ∗g (H). The same holds true for τ∗g
′(H), too.
Proof. No matter which player starts the game, at the end the cover function tq is a frac-
tional transversal. This implies the lower bounds τ∗g (H) ≥ τ∗(H) and τ∗g
′(H) ≥ τ∗(H).
Concerning a fractional transversal game G on H and the upper bounds in (i), we can
write the value of the game in the form |G| = W + W ′, where W and W ′ denote the
total sum of weights assigned by Edge-hitter and Staller, respectively. To keep the claimed
bounds, first Edge-hitter can fix an optimal fractional transversal f , i.e. one with |f | =
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 7
τ∗(H). After that, in his moves he can apply the strategy to play submoves (vij , wj) with
the largest possible weights wj which are not only allowed by (∗) but also respect the
inequalities ti−1(vij ) + wj ≤ f(vij ). If such a legal submove with a positive weight does
not exist anymore, then H is fully covered and the game is finished.
This strategy yields W ≤ τ∗(H), with strict inequality if the game is finished by Staller.
We also have W ′ ≤ W or W ′ ≤ W + 1, depending on whether the first move is made
by Edge-hitter or Staller, both with strict inequalities if the game is finished by Edge-hitter.
Since only one of the players can make the last move, the claimed strict upper bounds
follow.
For the proof of (ii) we apply the following result of Alon [1]: For every ϵ > 0 and
for any sufficiently large k, there is a k-uniform hypergraph H = (V, E) such that τ(H) ≥
(1 − ϵ) ln kk (|V | + |E|). On the other hand, a very simple fractional transversal f with
|f | = |V |/k may be constructed by assigning f(v) = 1/k to each vertex v ∈ V . Therefore,
τ∗(H) ≤ |V |k and we obtain
(1/2− ϵ) ln k < sup
H
τ(H)
2τ∗(H)
< sup
H
τ(H)
τ∗g (H)
≤ sup
H
τg(H)
τ∗g (H)
due to the obvious fact τ ≤ τg and the inequality τ∗g < 2τ∗ from (i). For τ∗g
′(H) the proof
is similar, by the second part of (i).
Proposition 3.2. The upper bounds in Proposition 3.1(i) are tight apart from an additive
constant at most 2.
Proof. Consider the complete bipartite graph G = Kk,k2 on k+k2 vertices as a 2-uniform
hypergraph. Clearly, τ∗(G) = k. In any submove of a fractional transversal game, while
G is not fully covered, Staller can always select a vertex from the bigger partite class.
Following this strategy, during k − 1 moves, Staller increases the sum of the loads by at
most (k − 1)k. As G has maximum degree k2, k − 1 moves of Edge-hitter increase the
loads by at most (k−1)k2. Hence, no matter whether Edge-hitter or Staller starts the game,
after 2k − 2 moves we have∑
E∈E
ℓ2k−2(E) ≤ (k − 1)k + (k − 1)k2 = k3 − k < |E| ,
therefore the game is not over yet. This shows τ∗g (G) > 2k − 2 = 2τ∗(G) − 2 and,
similarly, τ∗g
′(H) ≥ 2τ∗(G)− 1 follows if Staller starts the game.
A monotone property of the game fractional transversal number is expressed in the
following idea, which provides a useful tool in simplifying several arguments. Let a hy-
pergraph H with a pre-defined load function ℓ be given, which we consider as a non-zero
starting configuration. We ask about the value |G| of the game started by Edge-hitter, where
the game is finished when ℓ is completed to a load function under which H is fully covered.
The rules are the same as they were in the case of ℓ0 ≡ 0, but here we have ℓ0 = ℓ, while
the value of the game is still computed by starting with the cover function t0 ≡ 0. Under
these conditions and assuming that Edge-hitter starts the fractional transversal game G on
hypergraph H with the pre-defined ℓ, we consider the sets
UH|ℓ = {a ∈ R : Edge-hitter has a strategy that ensures |G| ≤ a} ,
LH|ℓ = {b ∈ R : Staller has a strategy that ensures |G| ≥ b}.
8 Ars Math. Contemp. 24 (2024) #P3.05
Then the game fractional transversal number with predefined load function ℓ is defined as
τ∗g (H|ℓ) = inf(UH|ℓ). It can be shown with a proof analogous to that of Proposition 2.1
that inf(UH|ℓ) = sup(LH|ℓ) always holds.
The corresponding value τ∗g
′(H|ℓ) is defined analogously for the Staller-start game on
H|ℓ.
The imagination strategy is a useful technique applied in many proofs when domination
and transversal games are considered (see e.g. [3, 6, 9, 15, 17, 20]). It was introduced
and first used in [7]; for a detailed explanation and examples we refer the reader to [5,
Chapter 2.2].
Theorem 3.3 (Continuation Principle). If ℓ and ℓ′ are load functions on the hypergraph
H = (V, E) such that ℓ(E) ≤ ℓ′(E) holds for every E ∈ E , then τ∗g (H|ℓ) ≥ τ∗g (H|ℓ′), and
similarly τ∗g
′(H|ℓ) ≥ τ∗g
′(H|ℓ′).
Proof. Assume for a contradiction that τ∗g (H|ℓ) < τ∗g (H|ℓ′), and choose two reals t1, t2
with τ∗(H|ℓ) < t1 < t2 < τ∗g (H|ℓ′). We use the imagination strategy between the
following two games:
Game 1: Edge-hitter plays on H|ℓ applying a strategy which ensures that the value of
the game is at most t1. Staller’s moves in Game 1 are defined according to her moves in
Game 2.
Game 2: Staller plays on H|ℓ′ applying a strategy which ensures that the value of the
game is at least t2. Edge-hitter’s moves in Game 2 are defined according to his moves in
Game 1.
Assume that Edge-hitter starts the game. He chooses his first move in Game 1 according
to the prescribed strategy. We copy this move into Game 2 if it is a legal move there, or
choose an appropriate replacement move for Edge-hitter in Game 2. In the next turn, Staller
replies with a move according to her prescribed strategy in Game 2 and we copy the same
move into Game 1. (We will see that it is always legal.) Then, Edge-hitter replies in Game 1
and we copy it or make the according move for Edge-hitter in Game 2. The two parallel
games continue this way until at least one of them is finished.
The moves essentially are copied (or interpreted) between Game 1 and Game 2 such
that ℓ(E) ≤ ℓ′(E) remains true for all E ∈ E after every move. If this inequality is valid
before Staller’s move in Game 2, then her next move in H|ℓ′ is legal in H|ℓ as well, so that
we can simply copy it into Game 1. The condition ℓ(E) ≤ ℓ′(E) for all E ∈ E clearly
remains valid for the new load functions.
Suppose now that the inequality ℓ(E) ≤ ℓ′(E) is true for all E ∈ E before Edge-
hitter’s move in Game 1. If it is legal, we simply copy it into Game 2 and the inequality
remains valid. In the other case one or more submoves (vik , wk) made in Game 1 are not
legal in Game 2. We then choose the maximum w′k such that (vik , w
′
k) is a legal submove
in Game 2. The remaining weight wk − w′k can be distributed between arbitrary vertices
such that the submoves are legal. Observe, however, that if this happens, all loads on the
edges incident with vik reach 1 after the submove (vik , w
′
k) in Game 2. We infer that
ℓ(E) ≤ ℓ′(E) remains true for all E ∈ E after Edge-hitter’s move.
It follows that the loads will never become smaller in Game 2 than the corresponding
ones in Game 1. Thus, the values g1 and g2 of Games 1 and 2 satisfy g1 ≥ g2. By the
strategies of the players, it is true that t1 ≥ g1 and g2 ≥ t2. We therefore obtain
t1 ≥ g1 ≥ g2 ≥ t2 > t1
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 9
and this contradiction proves τ∗g (H|ℓ) ≥ τ∗g (H|ℓ′).
The analogous conclusion can be reached in the Staller-start game as well, literally by
the same argument, deriving a contradiction from the assumption τ∗g
′(H|ℓ) < τ∗g
′(H|ℓ′).
We obtain the following immediate consequence.
Theorem 3.4. The game fractional transversal numbers for the Staller-start and for the
Edge-hitter-start games on H may differ by at most 1.
Proof. Consider the Staller-start game. Whatever Staller moves first, she assigns total
weight 1, and creates a situation which is at least as favorable for Edge-hitter as the all-
zero load at the beginning of the original transversal game. Then, due to Theorem 3.3,
Edge-hitter can ensure that the game ends using at most τ∗g (H) further weight. This proves
τ∗g
′(H) ≤ τ∗g (H) + 1.
Similarly, if Edge-hitter starts, after his first move he is in at least as favorable position
as with the all-zero load at the beginning of the Staller-start game. This proves the reverse
inequality τ∗g (H) ≤ τ∗g
′(H) + 1.
4 Infinite moves are not necessary
The definition of a legal move in the transversal game admits the option that a player splits
the value 1 into an infinite number of pieces; e.g., wk = 2−k. It turns out, however, that
each legal move on H = (V, E) is equivalent to a move which consists of at most |V |
submoves.
Theorem 4.1. Every legal move in a fractional transversal game can be replaced with a
legal move such that each vertex occurs in at most one submove of it and the two moves
result in the same load function.
Proof. First, consider a vertex v which occurs in two different submoves (vij , wj) and
(vik , wk) of a move. That is, v = vij = vik and we may assume j < k. By the condi-
tion (∗), there exists an edge E ∈ E such that v ∈ E and the second submove (vik , wk)
increases the load of E by exactly wk. If the submove (vij , wj) is deleted from the se-
quence and the weight wk is replaced by wj +wk in the kth submove, the submove and the
whole move remain legal and result in the same load function as before. Performing this
modification repeatedly we can achieve that every vertex occurs in either zero or exactly
one or infinitely many submoves of the move in question. This already proves the statement
if the move contains only a finite number of submoves.
Now, assume that the move is infinite. Then, the sequence of submoves can be split
into two, such that the first part is finite, and in the second infinite part every vertex
(which is present there) is repeated infinitely many times. Consider this infinite subse-
quence S = (vis , ws), . . . . By renaming the vertices of H if necessary, we may assume
that {v1, . . . , vℓ} is the set of the vertices which are present in S. We prove that the finite
sequence S′ = (v1,
∑
j: ij=1
wj), . . . , (vℓ,
∑
j: ij=ℓ
wj) is equivalent to S. Clearly, S and
S′ yield the same load function after the move. So, it is enough to prove that S′ is legal.
Assume for a contradiction that (vk,
∑
j: ij=k
wj) is not a legal submove in S′, and let k
be the smallest such index. Then, after the (k − 1)st submove of S′, every edge E which
contains vk has a load ℓ(E) > 1−
∑
j: ij=k
wj and, moreover, there is a positive constant
10 Ars Math. Contemp. 24 (2024) #P3.05
ϵ such that minvk∈E ℓ(E) +
∑
j: ij=k
wj = 1 + ϵ. Now, consider S again. There is an
index p = p(ϵ) such that
∑
j≥p wj < ϵ and hence, before the p
th submove of S, each edge
containing vk is fully covered. As vk occurs infinitely often in S, and also the occurrences
after the pth submove are legal, this is a contradiction.
5 Edge-hitter’s moves are transposable
We say that a finite move (vi1 , w1), . . . , (vik , wk) is transposable if for any permutation
β(1), . . . , β(k) of 1, . . . , k, the move (viβ(1) , wβ(1)), . . . , (viβ(k), wβ(k)) is legal. We will
show that from the point of view of Edge-hitter, we can restrict our attention to transposable
moves. Note that every transposable move is legal, but not conversely.
We first give a characterization of transposable moves:
Lemma 5.1. A move (vi1 , w1), . . . , (vik , wk), where wj > 0 for all 1 ≤ j ≤ k and
no vertices are repeated, is transposable if and only if the total weight constraint (∗∗) is
satisfied, and after performing the entire move, for every vertex vij ,
min
E∋vij
∑
vi∈E
t(vi) ≤ 1. (5.1)
Proof. A legal move must satisfy the two constraints (∗) and (∗∗).
The total weight constraint (∗∗) for a legal move is explicitly required in the lemma,
and it is insensitive to permuting the submoves.
Let us turn to (∗). If
∑
vi∈E t(vi) ≤ 1 for an edge E containing vij , then omitting the
submove (vij , wj) from the move we obtain
∑
vi∈E\{vij }
t(vi) ≤ 1−wj . Hence (vij , wj)
is a legal submove no matter when it is performed during the move. This means that the
move is transposable whenever the condition (5.1) is satisfied for all j.
In the other direction, assume that for some vij , the left-hand side of (5.1) is bigger
than 1. Consider a permutation in which (vij , wj) is the last submove. Then (vij , wj) is
not legal because (∗) is violated. Consequently the move is not transposable.
Theorem 5.2. If a finite legal move m = (vi1 , w1), . . . , (vik , wk) is not transposable in
the fractional transversal game, then it can be replaced by a transposable (and legal) move
after which no edge gets smaller load than after m.
Proof. First, consider the legal move m = (vi1 , w1), . . . , (vik , wk) and the move m
′ =
(vi2 , w2), . . . , (vik , wk), (vi1 , w1) that is obtained by the cyclic permutation β =
2, . . . , k, 1. It is clear that condition (∗) in the definition remains true for the first k − 1
submoves of m′ and consequently, these submoves are legal. For the last (and not nec-
essarily legal) submove, determine w∗1 as the maximum weight which results in a legal
submove with vi1 . If w
∗
1 ≥ w1, then m′ is legal and gives exactly the same load function
as m. If w∗1 < w1, then the same load function is obtained after the submove (vi1 , w
∗
1) as
after m, because in both cases every edge incident with vi1 is fully covered and the loads
of the other edges are unchanged.
In the latter case, the sum of the weights is decreased by w1−w∗1 . After this change, the
submove (vi1 , w
∗
1) will be legal in any permutation of (vi1 , w
∗
1), (vi2 , w2), . . . , (vik , wk).
That is, if a permutation is not legal after this replacement, this is due to another vertex.
The same is true if some weights ws are replaced by smaller weights.
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 11
We repeat this step for the modified sequence with permutation β = 3, . . . , k, 1, 2,
then with β = 4, . . . , k, 1, 2, 3, and so on, finally with β = k, 1, 2, . . . , k − 1, keeping
all modifications incrementally. Decreasing the weight of the last submove in each step
if necessary, at the end a legal transposable move m∗ is obtained, which yields the same
load function as m and satisfies
∑k
j=1 w
∗
j ≤
∑k
j=1 wj . If ∆ =
∑k
j=1 wj −
∑k
j=1 w
∗
j is
positive, we use the weight ∆ to increase the loads of some non-fully covered edges in an
arbitrary way. The total absolute change of weights is 2∆, or possibly less if the game is
over. Finally, we normalize the move by eliminating any multiple occurrences of vertices,
using Theorem 4.1.
The redistribution of ∆ and the normalization may lead to a move that is not transpos-
able. If so, we repeat the modification described above.
If the process terminates after a finite number of iterations, then the last version of the
move is transposable by construction, and the proof is complete. Otherwise we obtain an
infinite sequence ∆(1),∆(2), . . . of re-distributions from the total unit weight of the move.
The total load of edges increases by at least
∑
i≥1 ∆
(i); hence this sum converges because
altogether the total load is at most |E|.
On the other hand, the weight of a vertex changes by at most ∆(i) in the ith iteration,
hence the local changes in weight (at least one of which is negative in each iteration) in
absolute value sum up to at most 2
∑
i≥1 ∆
(i), and therefore their sum also converges.
Let m(i) denote the move constructed in the ith iteration, before the re-distribution of
the weight ∆(i). We know that this move is transposable. Let w(i)v denote the weight used
for vertex v in the corresponding submove of m(i), and set w(i)v = 0 if v does not appear in
this move.
We have shown that the limit of these weights w∗v = limi→∞ w
(i)
v = 0 exists. Let p
denote the number of vertices with a positive weight in w∗. Relabeling these vertices in
an arbitrary order, we define a move m∗ = (v1, w∗1), . . . , (vp, w
∗
p) with p submoves. By
continuity, the loads achieved by the moves m(i) converge to the corresponding loads after
the move m∗.
We claim that m∗ is transposable. This will complete the proof because the loads never
decrease, hence under w∗ no edge gets smaller load than by move m.
For showing that m∗ is transposable, we use the characterization of Lemma 5.1. The
inequality (5.1) follows from the fact that its left-hand side is a continuous function of the
weights.
Let us finally check that the total weight constraint (∗∗) is satisfied: Since
∑
v w
(i)
v ≤ 1
for all i, this inequality is satisfied in the limit. If in some iteration, the current move
terminates the game (i.e., each edge gets load at least 1 while the total weight in the move
is at most 1), this will hold in all successive moves, since the loads never decrease, and
hence it holds also for m∗, by continuity. Therefore, we need to show
∑
v w
∗
v = 1 only
when none of the moves terminate the game. In this case, the difference 1 −
∑
v w
(i)
v is
bounded by ∆i, which goes to 0, and hence
∑
v w
∗
v = 1 in the limit.
Remark 5.3. Based on Theorem 5.2, Edge-hitter may restrict his strategy to transposable
moves. On the other hand, the result suggests that Staller is advised to perform moves, if
possible, which are ‘very non-transposable’ in a sense.
12 Ars Math. Contemp. 24 (2024) #P3.05
6 Algorithm for computing the value of the game
We consider an equivalent version of the game, the structured game, which is easier to
analyze.
Each move consists of n + 1 rounds. Each round consists of n submoves, which are
dedicated to the vertices v1, . . . , vn in succession. In each submove, the player whose turn
it is can decide the amount w, the weight spent in the submove, by which the cover value of
t(vi) is increased, subject to the usual rules: The increase must be useful, i.e. each submove
must satisfy the condition (∗), and it must be within the budget constraint of total weight 1
to be spent per move. It is possible to skip a submove by simply choosing w to be zero.
The first n rounds are identical, but the last round is special: In each submove, the
weight is greedily chosen as the largest possible legal weight, hence not allowing any free-
dom in choosing w for the player in those submoves. This ensures that the whole move
spends a total weight of 1 unless a cover is obtained.
There are n moves, alternating between the two players. This is enough to ensure that a
cover is constructed when the game terminates. Every move consists of n2 + n submoves,
and in total, the game consists of N = n3 + n2 submoves. We illustrate this for a small
example with n = 4 vertices, where the Edge-hitter starts. The sequence of submoves is
H1, H2, H3, H4; H1, H2, H3, H4; H1, H2, H3, H4; H1, H2, H3, H4; G1, G2, G3, G4;
S1, S2, S3, S4; S1, S2, S3, S4; S1, S2, S3, S4; S1, S2, S3, S4; G1, G2, G3, G4;
H1, H2, H3, H4; H1, H2, H3, H4; H1, H2, H3, H4; H1, H2, H3, H4; G1, G2, G3, G4;
S1, S2, S3, S4; S1, S2, S3, S4; S1, S2, S3, S4; S1, S2, S3, S4; G1, G2, G3, G4.
Here Hi denotes a move of Edge-hitter for vertex i, and Si denotes a move of Staller for
vertex i. The greedy moves are denoted by Gi.
We do not stipulate as part of the rules that the whole budget of 1 unit must be spent
during a move. This capacity is only an upper bound. It is still true that the whole budget
is spent in each move if the game is played from the beginning. However, this arises as a
consequence of the new setup, due to the greedy moves.
As soon as a cover is found, the rules imply that no more weight can be spent, and thus
the game is effectively over.
Lemma 6.1. The structured game has the same value as the original game.
Proof. According to Theorem 4.1, we can assume that every vertex occurs at most once in
a move. We can realize this in the structured game by selecting one vertex per round and
leaving the weight at 0 otherwise. Thus, the structured game does not restrict the players’
strategies, when compared to the original game. On the other hand, the structured game
does not give the players more power: The greedy moves ensure that the total weight of 1
is used as long as it is possible.
Example for the structured game. Consider an Edge-hitter-start game on C4 with strate-
gies of the players as described in Section 2.1. A corresponding structured game, where
we follow the idea in the proof of Lemma 6.1, can be given as follows.
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 13
Edge-hitter’s first move: (v1, 14 ), (v2, 0), (v3, 0), (v4, 0);
(v1, 0), (v2, 14 ), (v3, 0), (v4, 0);
(v1, 0), (v2, 0), (v3, 14 ), (v4, 0);
(v1, 0), (v2, 0), (v3, 0), (v4, 14 );
(v1, 0), (v2, 0), (v3, 0), (v4, 0).
Staller’s first move: (v1, 0), (v2, 0), (v3, 12 ), (v4, 0);
(v1, 0), (v2, 0), (v3, 0), (v4, 12 );
(v1, 0), (v2, 0), (v3, 0), (v4, 0);
(v1, 0), (v2, 0), (v3, 0), (v4, 0);
(v1, 0), (v2, 0), (v3, 0), (v4, 0).
Edge-hitter’s second move: (v1, 0), (v2, 16 ), (v3, 0), (v4, 0);
(v1, 0), (v2, 0), (v3, 0), (v4, 0);
(v1, 0), (v2, 0), (v3, 0), (v4, 0);
(v1, 0), (v2, 0), (v3, 0), (v4, 0);
(v1,
1
3 ), (v2, 0), (v3, 0), (v4, 0).
For demonstration, the last move makes use of a greedy submove.
By Theorem 5.2, it is not a disadvantage for Edge-hitter restricting himself to
transposable moves. Consequently, his submoves can always be performed in the order
(v1, w1), . . . , (vk, wk), and a single round H1, H2, . . . ,Hn followed by n greedy sub-
moves would be a sufficient model for Edge-hitter’s moves. For simplicity, we have how-
ever chosen to treat the two players uniformly. Note that the greedy submoves are necessary
also in case of Edge-hitter. Otherwise, for example, he might pass on the first move and
transform the game to the Staller-start version, which sometimes admits a smaller game
value (as in the example of C4).
Consider the situation after the jth submove, 0 ≤ j ≤ N . Let x⃗ ∈ [0, 1]E be an arbitrary
load vector, and let r ∈ [0, 1] be the budget for the current move that is still available. If j
is written in the form j = k(n2 + n) + i, i.e. k = ⌊ jn2+n⌋ and 0 ≤ i < n
2 + n, then 1− r
is the total weight spent in the last i submoves.
We define
Tj(x⃗, r)
as the sum of weights spent during the remaining part of the game, if both players play
optimally, starting from the current situation. If j is large and the entries of x⃗ are small,
it may happen that a complete fractional cover is not reached, because the game neces-
sarily ends after the nth round. Nevertheless, we have chosen our definition because it
makes Tj well-defined for arbitrary x⃗ and r. (The definition of Tj(x⃗, r) is related to the
game fractional transversal number with predefined load function used in the proof of the
Continuation Principle (Theorem 3.3)6.)
The value of the original game is T0(⃗0, 1).
We will derive a backward recursion for the functions Tj , and thus show that they are
piecewise linear and continuous.
6In particular, if the jth submove is the last submove in a move of Staller and ℓ is the load function corre-
sponding to x⃗, then we would expect Tj(x⃗, 1) to be τ∗g (H|ℓ). However this does not hold in general because, as
just discussed, the structured game may terminate too early.
14 Ars Math. Contemp. 24 (2024) #P3.05
Given j, we know the type of the jth submove (H , S, or G) and the vertex vi to which
it applies. We denote the maximum permitted weight by
wmaxi (x⃗, r) = min{r,max{ 1− xE | E ∋ vi }} , (6.1)
where xE denotes the entry of x⃗ that corresponds to the edge E ∈ E . For the result of
increasing the cover value of vi by w we write
updatei(x⃗, w) = x⃗
′ with x′E =
{
xE , if vi /∈ E,
min{1, xE + w}, if vi ∈ E.
(6.2)
With these definitions, the recursion for a submove Hi for Edge-hitter can be written easily:
Tj−1(x⃗, r) = min{w + Tj(updatei(x⃗, w), r − w) | 0 ≤ w ≤ wmaxi (x⃗, r) } (6.3)
If the submove is for Staller (Si), the recursion is the same as (6.3), except that min is
replaced by max. In the greedy submoves Gi, we always choose w = wmaxi (x⃗, r):
Tj−1(x⃗, r) = w
max
i (x⃗, r) + Tj(updatei(x⃗, w
max
i (x⃗, r)), r − wmaxi (x⃗, r)) (6.4)
The last greedy submove Gn of each move is an exception: Since a different move is about
to start, the budget r is reset to 1. Thus, when j is a multiple of n2 + n, then
Tj−1(x⃗, r) = w
max
n (x⃗, r) + Tj(updaten(x⃗, w
max
n (x⃗, r)), 1). (6.5)
As the recursion anchor, we use the value after the final move, which is simply
TN (x⃗, r) = 0. (6.6)
Theorem 6.2. Each function Tj(x⃗, r) for 0 ≤ j ≤ N is a piecewise linear continuous
function with finitely many linear pieces defined on [0, 1]E × [0, 1]. Moreover, all Tj are
rational in the sense that each linear piece has rational coefficients and rational constant
part. As a consequence, the boundaries between regions of the domain with different linear
functions can be described by linear equations with rational coefficients.
Proof. We will call a function with all the desired properties — piecewise linear, continu-
ous, and rational, with finitely many linear pieces — a PLCR function.
The proof proceeds by backward recursion from TN down to T0. The function TN
from (6.6) is obviously PLCR.
The sum, difference, maximum, or minimum of two PLCR functions is again PLCR,
and the same holds true when substituting one PLCR function into another. It follows
directly that the functions wmaxi and updatei are PLCR functions on the domain [0, 1]
E ×
[0, 1]. This allows us to perform the induction step in the recursions (6.4)–(6.5) for Gi.
In the recursion (6.3) we additionally have a minimization (or, in the analogous recur-
sion for Staller, a maximization) over some range of values w. It has the form
min{F (x⃗, r, w) | 0 ≤ w ≤ wmaxi (x⃗, r) }
with the PLCR function
F (x⃗, r, w) := w + Tj(updatei(x⃗, w), r − w)
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 15
To get rid of the varying upper bound on w, we rewrite the recursion in terms of another
PLCR function
F̂ (x⃗, r, w) = F (x⃗, r,min{w,wmaxi (x⃗, r)}
as
Tj−1(x⃗, r) = min{ F̂ (x⃗, r, w) | 0 ≤ w ≤ 1 }.
Lemma 6.3 below establishes that Tj−1 is a PLCR function.
The same argument applies to the recursion for Staller (Si), where min is replaced by
max.
Lemma 6.3. Suppose that F̂ (y, w) : [0, 1]m × [0, 1] → R is a PLCR function. Then the
function T (y) : [0, 1]m → R defined by minimizing over w:
T (y) := min{ F̂ (y, w) | 0 ≤ w ≤ 1 } (6.7)
is also a PLCR function.
Proof. We first show that T is continuous. Since F̂ is PLCR, it is Lipschitz-continuous.
Let L be its Lipschitz constant with respect to the ∞-norm. (We can compute L as the
maximum L1-norm of all coefficient vectors of the linear pieces of F̂ .) It follows that the
function T in (6.7) is also Lipschitz-continuous with Lipschitz-constant L. To see this, let
∥y0 − y1∥ ≤ ε, and let T (y0) = F̂ (y0, w0) for some w0. Then T (y1) ≤ F̂ (y1, w0) ≤
F̂ (y0, w0) + Lε = T (y0) + Lε. The converse bound T (y0) ≤ T (y1) + Lε follows in the
same way.
We still need to show that T is piecewise linear. For an intuitive way to see this, one can
interpret the minimization over w geometrically. The graph of F̂ : [0, 1]m× [0, 1] → R is a
subset of Rm+2. Taking the minimum over all w amounts to projecting away the coordinate
corresponding to w and taking the lower envelope (with respect to the last coordinate) in the
projection in Rm+1. Figure 2 shows a two-dimensional illustration. This picture can also be
interpreted as a three-dimensional view of the graph of a bivariate function F̂ (y, w) when
the viewing direction is parallel to the w-axis. (In this hypothetical example, the resulting
minimum is discontinuous; this cannot happen when F̂ is continuous and its domain is the
box [0, 1]m × [0, 1].)
Formally, we conduct the proof as follows. We know that the domain [0, 1]m+1 of F̂
splits into finitely many rational convex (m + 1)-dimensional polytopes P on which F̂ is
linear:
F̂ (y, w) = aP y + bPw + cP , for (y, w) ∈ P
for some rational coefficient vector aP and rational coefficients bP and cP . We can thus
write T (y) as the minimum of finitely many functions TP (y) of the form
TP (y) := min{ aP y + bPw + cP | 0 ≤ w ≤ 1, (y, w) ∈ P }, (6.8)
where the minimum of an empty set is taken as ∞.
For fixed y, the minimum in (6.8) depends on the sign of bP . If bP > 0, the minimum
is achieved on a boundary point that lies on some facet P ′ of P whose outer normal has
negative w-coordinate. On such a facet, w can be expressed as a linear function of y, and
thus, TP can be written as a linear function
TP ′(y) = aP ′y + cP ′ , for y ∈ P̄ ′, (6.9)
16 Ars Math. Contemp. 24 (2024) #P3.05
y
{ (y, F̂ (y, w)) | 0 ≤ w ≤ 1 }
F̂
0 1
Figure 2: The lower envelope of a polyhedral set in 2 dimensions (m = 1).
where P̄ ′ is the projection of the facet P ′ to [0, 1]m. Thus, TP (y) is the minimum of finitely
many functions TP ′(y), with the understanding that TP ′(y) is taken as ∞ when y is outside
its domain P̄ ′.
The situation is similar for bP < 0. When bP = 0, then F̂ does not depend on w and
we can simply write
TP (y) = aP y + cP , for y ∈ P̄ , (6.10)
where P̄ is the projection of P .
In summary, the function T (y) can be written as the minimum of finitely many pieces
TP (y), each of which can in turn be written as the minimum of finitely many linear pieces
(6.9) or (6.10). All these pieces have rational coefficients and rational domain boundaries,
and since continuity of T has already been established, the PLCR property of T follows.
The proof of Theorem 6.2 is constructive and, in principle, it provides an algorithm for
computing the value T0(⃗0, 1) of the game. From this, we obtain the following important
corollary.
Theorem 6.4. For every finite hypergraph H = (V, E), the game fractional transversal
number τ∗g (H) and its Staller-start version τ∗g
′(H) are rational. Moreover, each player in
every step has an optimal move with only rational weights, provided that the weights in all
previous submoves were rational.
Remark 6.5. It is not true in general that every optimal strategy uses only rational weights.
A simple counterexample is the graph C4 (Example 1 from Section 2.1), where Staller can
start by placing x and 1 − x on two vertices with any x ∈ [0, 1], no matter if x is rational
or irrational.
7 Concluding remarks and open problems
Putting the fractional domination game [15] into a more general context, in this paper
we introduced the fractional transversal game on hypergraphs. Among other results, we
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 17
proved that the game value is rational, and both players have optimal strategies using ratio-
nal weights and with a finite number of submoves. Since a dominating set of a graph is a
transversal of the closed neighborhood hypergraph, and a total dominating set is a transver-
sal of the open neighborhood hypergraph, the following consequence is immediate.
Theorem 7.1. The fractional versions of both the domination game and the total domi-
nation game have rational game values (game fractional domination number and game
fractional total domination number) on every graph.
We conclude this paper with some conjectures and open questions.
Conjecture 7.2. If each of the first 2k − 1 (k ≥ 1) moves was an integer move in the
fractional transversal game, i.e. of the form (vi1 , 1), then Staller has an integer move in the
(2k)th turn, which is optimal in the fractional transversal game.
This means that fractional moves would be advantageous for Edge-hitter only. If true
then this conjecture implies the following weaker one.
Conjecture 7.3. For every hypergraph H , τ∗g (H) ≤ τg(H).
Perhaps the following stronger version of Conjecture 7.2 is also true.
Conjecture 7.4. Starting from any cover function, there is an optimal strategy for Staller
where, in every submove, she always spends the largest legal weight.
These conjectures could be approached by implementing the algorithm that is implicit
in the proof of Theorem 6.2 by computer. We have not derived an estimate for the com-
plexity (number of pieces) of the piecewise linear continuous functions Tj(x⃗, r) that are
involved in the construction. If the growth of the complexity is not too steep, there is hope
to solve some examples of moderate size, beyond the range of small examples that we
considered in Section 2.1, and this could shed some light on the conjectures.
One would naturally expect that T0(x⃗, r) is monotonically decreasing in x⃗, for fixed r,
and moreover, that it is Lipschitz-continuous with Lipschitz constant 1. In other words, in
every linear piece, the coefficient of each variable xi is between 0 and −1. We have not
explored these properties.
Acknowledgement
We are grateful to Gábor Tardos for helpful discussions.
ORCID iDs
Csilla Bujtás https://orcid.org/0000-0002-0511-5291
Günter Rote https://orcid.org/0000-0002-0351-5945
Zsolt Tuza https://orcid.org/0000-0003-3235-9221
References
[1] N. Alon, Transversal numbers of uniform hypergraphs, Graphs Comb. 6 (1990), 1–4, doi:
10.1007/BF01787474, https://doi.org/10.1007/BF01787474.
18 Ars Math. Contemp. 24 (2024) #P3.05
[2] M. Borowiecki, A. Fiedorowicz and E. Sidorowicz, Connected domination game, Appl. Anal.
Discrete Math. 13 (2019), 261–289, doi:10.2298/AADM171126020B, https://doi.org/
10.2298/AADM171126020B.
[3] B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza and
M. Vizer, The variety of domination games, Aequationes Math. 93 (2019), 1085–1109, doi:10.
1007/s00010-019-00661-w, https://doi.org/10.1007/s00010-019-00661-w.
[4] B. Brešar, P. Dorbec, S. Klavžar and G. Košmrlj, Domination game: effect of edge- and vertex-
removal, Discrete Math. 330 (2014), 1–10, doi:10.1016/j.disc.2014.04.015, https://doi.
org/10.1016/j.disc.2014.04.015.
[5] B. Brešar, M. A. Henning, S. Klavžar and D. F. Rall, Domination Games Played on Graphs,
SpringerBriefs in Mathematics, Springer, Cham, 2021, doi:10.1007/978-3-030-69087-8,
https://doi.org/10.1007/978-3-030-69087-8.
[6] B. Brešar, S. Klavžar, G. Košmrlj and D. F. Rall, Guarded subgraphs and the domination game,
Discrete Math. Theor. Comput. Sci. 17 (2015), 161–168, doi:10.46298/dmtcs.2123, https:
//doi.org/10.46298/dmtcs.2123.
[7] B. Brešar, S. Klavžar and D. F. Rall, Domination game and an imagination strategy, SIAM
J. Discrete Math. 24 (2010), 979–991, doi:10.1137/100786800, https://doi.org/10.
1137/100786800.
[8] Cs. Bujtás, General upper bound on the game domination number, Discrete Appl. Math.
285 (2020), 530–538, doi:10.1016/j.dam.2020.06.018, https://doi.org/10.1016/j.
dam.2020.06.018.
[9] Cs. Bujtás, M. A. Henning and Zs. Tuza, Transversal game on hypergraphs and the 3
4
-
conjecture on the total domination game, SIAM J. Discrete Math. 30 (2016), 1830–1847, doi:
10.1137/15M1049361, https://doi.org/10.1137/15M1049361.
[10] Cs. Bujtás, M. A. Henning and Zs. Tuza, Bounds on the game transversal number in hy-
pergraphs, European J. Comb. 59 (2017), 34–50, doi:10.1016/j.ejc.2016.07.003, https:
//doi.org/10.1016/j.ejc.2016.07.003.
[11] Cs. Bujtás, V. Iršič and S. Klavžar, Perfect graphs for domination games, Ann. Comb.
25 (2021), 133–152, doi:10.1007/s00026-021-00523-w, https://doi.org/10.1007/
s00026-021-00523-w.
[12] Cs. Bujtás, V. Iršič and S. Klavžar, 1/2-conjectures on the domination game and claw-free
graphs, European J. Comb. 101 (2022), Paper No. 103467, 17 pp., doi:10.1016/j.ejc.2021.
103467, https://doi.org/10.1016/j.ejc.2021.103467.
[13] Cs. Bujtás, B. Patkós, Zs. Tuza and M. Vizer, Domination game on uniform hypergraphs, Dis-
crete Appl. Math. 258 (2019), 65–75, doi:10.1016/j.dam.2018.11.013, https://doi.org/
10.1016/j.dam.2018.11.013.
[14] Cs. Bujtás and Zs. Tuza, The disjoint domination game, Discrete Math. 339 (2016), 1985–
1992, doi:10.1016/j.disc.2015.04.028, https://doi.org/10.1016/j.disc.2015.
04.028.
[15] Cs. Bujtás and Zs. Tuza, Fractional domination game, Electron. J. Comb. 26 (2019), Paper No.
4.3, 17 pp., doi:10.37236/8730, https://doi.org/10.37236/8730.
[16] M. A. Henning and W. B. Kinnersley, Domination game: a proof of the 3/5-conjecture for
graphs with minimum degree at least two, SIAM J. Discrete Math. 30 (2016), 20–35, doi:
10.1137/140976935, https://doi.org/10.1137/140976935.
[17] M. A. Henning, S. Klavžar and D. F. Rall, Total version of the domination game, Graphs Comb.
31 (2015), 1453–1462, doi:10.1007/s00373-014-1470-9, https://doi.org/10.1007/
s00373-014-1470-9.
Cs. Bujtás et al.: Optimal strategies in fractional games: vertex cover and domination 19
[18] M. A. Henning and D. F. Rall, The enclaveless competition game, Ars Math. Contemp.
20 (2021), 129–142, doi:10.26493/1855-3974.2227.e1a, https://doi.org/10.26493/
1855-3974.2227.e1a.
[19] V. Iršič, Effect of predomination and vertex removal on the game total domination number of
a graph, Discrete Appl. Math. 257 (2019), 216–225, doi:10.1016/j.dam.2018.09.011, https:
//doi.org/10.1016/j.dam.2018.09.011.
[20] W. B. Kinnersley, D. B. West and R. Zamani, Extremal problems for game domination
number, SIAM J. Discrete Math. 27 (2013), 2090–2107, doi:10.1137/120884742, https:
//doi.org/10.1137/120884742.
[21] S. Klavžar and D. F. Rall, Domination game and minimal edge cuts, Discrete Math.
342 (2019), 951–958, doi:10.1016/j.disc.2018.12.001, https://doi.org/10.1016/j.
disc.2018.12.001.
[22] G. Košmrlj, Domination game on paths and cycles, Ars Math. Contemp. 13 (2017), 125–136,
doi:10.26493/1855-3974.891.e93, https://doi.org/10.26493/1855-3974.891.
e93.
[23] K. Xu, X. Li and S. Klavžar, On graphs with largest possible game domination number, Discrete
Math. 341 (2018), 1768–1777, doi:10.1016/j.disc.2017.10.024, https://doi.org/10.
1016/j.disc.2017.10.024.