ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.04
https://doi.org/10.26493/1855-3974.2710.f3d
(Also available at http://amc-journal.eu)
Variants of the domination number for flower
snarks
Ryan Burdett, Michael Haythorpe * , Alex Newcombe
Flinders University, 1284 South Road, Tonsley Park, SA, Australia
Received 25 October 2021, accepted 14 July 2023, published online 8 July 2024
Abstract
We consider the flower snarks, a widely studied infinite family of 3–regular graphs. For
the Flower snark Jn on 4n vertices, it is trivial to show that the domination number of Jn is
equal to n. However, results are more difficult to determine for variants of domination. The
Roman domination, weakly convex domination, and convex domination numbers have been
determined for flower snarks in previous works. We add to this literature by determining
the independent domination, 2-domination, total domination, connected domination, upper
domination, secure domination and weak Roman domination numbers for flower snarks.
Keywords: Flower, snarks, domination, variants, secure.
Math. Subj. Class. (2020): 05C69
1 Introduction
Consider a graph G containing the vertex set V and edge set E. A subset of the vertices
S ⊂ V is said to be a dominating set if every vertex in V \S is adjacent to at least one vertex
in S. Then, the domination problem is to determine the size of the smallest dominating set
in a given graph G, which is known as the domination number of G and is denoted by
γ(G).
There are obvious real-world applications for the domination problem. For example,
suppose that the vertices of a graph correspond to locations in a secure site, and that each
location needs to remain under observation by guards. If a guard at one location is able
to simultaneously observe another, there is an edge between the corresponding vertices.
Then, by placing guards at the sites corresponding to any dominating set, all locations are
under observation. Clearly, it is desirable to do so with as few guards as possible.
*Corresponding author.
E-mail addresses: ryan.burdett@flinders.edu.au (Ryan Burdett), michael.haythorpe@flinders.edu.au
(Michael Haythorpe), alex.newcombe@flinders.edu.au (Alex Newcombe)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P3.04
However, in many real-world applications, the definition of domination may be unsuit-
able in some way, and so variants of domination have been described to handle such cases.
Continuing the example in the previous paragraph, suppose that the guards carry out their
observation from the top of large towers. The vantage point from these towers enables
them to observe adjacent locations, but does not permit them to observe their own location.
Then, their location would need to be observed by a guard at an adjacent location. In such a
situation, we are seeking not a dominating set, but a total dominating set, which we define
formally now along with several other variants of dominating sets that we will consider in
this manuscript.
Definition 1.1. Consider a dominating set S ⊆ V . Then:
• S is a (weakly) convex dominating set if S is (weakly) convex in G.
• S is an independent dominating set if S is an independent set in G.
• S is a minimal dominating set if any proper subset of S is not a dominating set.
• S is a 2-dominating set if any vertex v ̸∈ S is adjacent to at least two vertices in S.
• S is a total dominating set if every vertex in V is adjacent to at least one vertex in S.
• S is a connected dominating set if the subgraph of G induced by the vertices in S is
connected.
• S is a secure dominating set if, for every vertex v ∈ V \ S, there exists a vertex
w ∈ S such that vw ∈ E, and (S \ {w}) ∪ {v} is a dominating set.
Analogously to the domination number, we define γwcon(G) to be the weakly convex
domination number, γcon(G) to be the convex domination number, i(G) to be the inde-
pendent domination number, γ2(G) to be the 2-domination number, γt(G) to be the total
domination number, γc(G) to be the connected domination number, and γs(G) to be the
secure domination number. We also define the upper domination number, Γ(G), as follows.
Definition 1.2. The upper domination number, denoted by Γ(G), is equal to the size of the
largest minimal dominating set.
In addition, we consider two more variants of domination. Suppose that for our graph
G, we have a function f : V → {0, 1, 2}. Then, the weight of f , denoted w(f), is equal to∑
v∈V f(v).
Definition 1.3. f is a Roman dominating function on G if it satisfies the condition that
every vertex v for which f(v) = 0 is adjacent to at least one vertex w for which f(w) = 2.
In the following definition, we say that a vertex v is undefended with respect to f if
f(v) = 0 and for every vertex w adjacent to v, f(w) = 0.
Definition 1.4. f is a weak Roman dominating function on G if, for every vertex v such
that f(v) = 0, there is at least one vertex w, adjacent to v and satisfying the following: if
we define a new function g : V → {0, 1, 2} defined by g(v) = 1, g(w) = f(w) − 1, and
g(u) = f(u) for all u ̸= {v, w}, then there are no undefended vertices with respect to g.
R. Burdett et al.: Variants of the domination number for flower snarks 3
Then, the Roman domination number γR(G) is the minimum weight over all Roman
dominating functions, and equivalently for the weak Roman domination number γr(G). It
is worth noting that if we further demand that f(v) ≤ 1 for all v ∈ V then weak Roman
domination is equivalent to secure domination. Hence, it is clear that γr(G) ≤ γs(G).
Domination numbers are known for some infinite families of graphs. Other than trivial
results such as for paths or cycles, perhaps the most famous result is the sprawling effort
over a 27 year period [2, 8, 14, 16, 20, 36] to provide a complete characterisation of domi-
nation numbers for grid graphs G(n,m) of all possible sizes, consisting of 23 special cases
before settling into a standard formula for n,m ≥ 16. Other results for domination include
generalized Petersen graphs [13, 24, 41], Cartesian products involving cycles [1, 9, 28],
King graphs [40], Latin square graphs [29], hypercubes [3], Sierpiński graphs [34], Knödel
graphs [12], and various graphs from chemistry [26, 32], among others.
However, far fewer results are known for variants of domination beyond trivial results
such as for paths, cycles, stars, wheels, or complete graphs. We summarise the most note-
worthy of these results for the variants of domination considered in this paper. For upper
domination, results are known for various graphs based on chessboards [4, 11, 18, 39, 40].
For total domination, results are known for some grid graphs G(n,m) (for n ≤ 6) [15, 21],
Knödel graphs [27], and various graphs from chemistry [26]. For connected domination,
results are known for trees [33], circulant graphs [35], Centipede graphs [38], and various
graphs from chemistry [26]. For weak Roman domination, results are known for various
graphs based on chessboards [30], Cartesian products involving complete graphs [37], and
Helm graphs and Web graphs [23]. For secure domination, results are known for some grid
and torus graphs (for n ≤ 3) [17], various Cartesian products of stars, cycles, paths and
complete graphs [37], and middle graphs [31].
In recent works, the following results were shown for flower snarks (which will be
defined in the next section).
Theorem 1.5 ([25, Maksimovic et al. (2018)], [22, Kratica et al. (2020)]). Consider the
flower snark Jn, for n ≥ 3. Then we have γR(Jn) = γwcon(Jn) = 2n, and γcon(Jn) =
4n.
We now add to the above literature by proving the following additional results for flower
snarks:
Theorem 1.6. Consider the flower snark Jn, for n ≥ 3. Then,
γ(Jn) = i(Jn) = n, γs(Jn) = γr(Jn) =
⌈
3n+ 1
2
⌉
,
γ2(Jn) =
{⌈
5n
3
⌉
, if n ̸= 1 mod 3,
5n+4
3 , if n = 1 mod 3,
γt(Jn) =
{⌈
3n
2
⌉
, if n ̸= 2 mod 4,
3n
2 + 1, if n = 2 mod 4,
γc(Jn) = Γ(Jn) =
{
2n, if n is even,
2n− 1, if n is odd.
In most cases, the proofs will be by induction, and hence it will be necessary to first
prove the results for some number of base cases. Rather than provide these proofs here, we
will simply use mixed-integer linear programming formulations of each variant of domina-
tion from literature to handle the base cases.
4 Ars Math. Contemp. 24 (2024) #P3.04
2 Flower snarks
The chromatic index of a graph is the minimum required number of colours to color the
edges of the graph, such that no two incident edges have the same colour. By Vizing’s
theorem, it is known that all 3–regular graphs have chromatic index 3 or 4. The latter
case is rare, and simple, connected, bridgeless 3–regular graphs with chromatic index 4 are
called snarks. It is common to further add the restriction that the girth should be at least
5, with such graphs known as nontrivial snarks. Flower snarks [19], discovered by Isaacs
in 1975, were the first known infinite family of nontrivial snarks, and are denoted by Jn.
They are defined as follows.
Definition 2.1 (Flower snarks). For n ≥ 3, take the union of n copies of K1,3. Denote the
degree 3 vertex in the i-th copy as ai, and the other three vertices in the i-th copy as bi, ci
and di. Then construct an n-cycle through vertices b1, b2, . . . , bn, and a 2n-cycle through
vertices c1, c2, . . . , cn, d1, d2, . . . , dn.
In order to have the properties of a nontrivial snark, n must be odd and n ≥ 5. However,
for other values of n ≥ 3 a 3–regular graph is nonetheless obtained by this construction. In
this paper we will consider all n ≥ 3, and for convenience we will refer to all of them as
flower snarks.
For the remainder of this document, we will consider various kinds of dominating sets
of flower snarks. As such, it is convenient to go over some brief terms and notation here.
Recall that Jn contains n copies of K1,3. We will refer to the i-th copy as J i, and its four
vertices as ai, bi, ci and di. Note that this notation does not include n, as typically n will be
fixed in our considerations. Also, we will say that a copy J i has weight k in a dominating
set S, if S contains k vertices from J i. We will use the term pattern to describe a sequence
of weights of consecutive copies of Jn in S. For example, if we say that S contains the
pattern 121, it means there is a set of three consecutive copies J i−1, J i, J i+1 which have
weights 1, 2 and 1 respectively in S. Further to this, in a set of consecutive copies of Jn,
we will use the term configuration to describe the specific allocation of its vertices to S.
Finally, we will define wSi to be equal to the number of copies with weight i in S.
Flower snarks can be visualised in various ways. A common method is to distribute the
copies of K1,3 in a circle, using curved edges for the 2n-cycle and straight edges elsewhere.
We display one such drawing of Jn in part (a) of Figure 1, for n = 7. However, for our
purposes it will be convenient to focus only on a small section of a flower snark at a time,
and so we will use the drawing style displayed in part (b) of Figure 1, with each copy
displayed vertically. As indicated in Figure 1 we will assume that in these drawings, the
bottom vertex in copy J i is bi, followed by ai, ci and di. When useful to avoid confusion,
a label will be given above each copy.
It is worth noting that, when viewing only a section of Jn, vertices bi, ci and di are all
essentially equivalent, and this will be useful in simplifying many of the upcoming proofs.
In a global sense this is not the case, as there is a “twist” in the final copy in which cn links
to d1, and dn links to c1. However, due to the symmetry of the flower snark, when viewing
any copy locally we can choose to relabel the vertices so that this twist occurs elsewhere in
the graph. Hence, in the arguments that follow, whenever we are viewing only a portion of
the graph we will always assume that the twist occurs elsewhere in the graph.
Various proofs in this paper will go as follows. We will begin with a set of copies of Jn
for which the pattern is known, as well as possibly knowing in advance that some vertices
are either in S, or not in S. From there, depending on the variant of domination being
R. Burdett et al.: Variants of the domination number for flower snarks 5
(a)
a
b
c
d
J1 J2 J3 J4 J5 J6
(b)
Figure 1: In part (a) a common drawing of the flower snark J7. In part (b), a section of a
larger flower snark consisting of six copies.
considered, and the structure of Jn, we will go on to prove that certain vertices either must
be in S, or must not be in S. For these proofs, figures will be provided, using the following
convention. The pattern known in advance will be indicated by listing the corresponding
weight underneath each copy. Vertices which are known in advance to be in S will be
marked with , and vertices which are known in advance not to be in S will be marked
with . Then, vertices which are subsequently shown (up to equivalence) to be in S will be
marked with , while vertices which are subsequently shown not to be in S will be marked
with . We demonstrate this convention with a simple example.
Example 2.2. Suppose we have four copies J1, J2, J3, J4 which meet the pattern 1111,
and that we know that d2 ∈ S and c1 ̸∈ S. This situation is displayed in Figure 2. Clearly,
since d2 ∈ S and J2 has weight 1, we know that a2 ̸∈ S, b2 ̸∈ S, and c2 ̸∈ S. These
three are marked with in Figure 2 as no argument was needed to establish they are not in
S. Then, the only remaining vertex which can dominate c2 is c3, and hence c3 ∈ S. Since
this was argued in the proof, c3 is marked with a in Figure 2. Also, since J3 has weight
1 the vertices a3, b3, and d3 cannot be in S, and so they are marked with . Then, the
only remaining vertex which can dominate b2 is b1, which we similarly mark in Figure 2.
Finally, the only remaining vertex which can dominate b3 is b4, which we again mark in
Figure 2. Hence, we now know exactly which vertices in J1, J2, J3, J4 are contained in
S.
a
b
c
d
J1 J2 J3 J4
1 1 1 1
Figure 2: The situation described in Example 2.2.
To conclude this section, we note that it is trivial to determine the domination and
independent domination numbers for flower snarks.
Lemma 2.3. For n ≥ 3, we have γ(Jn) = i(Jn) = n.
Proof. The graph Jn contains n copies of K1,3. For each copy J i, the vertex ai is ad-
jacent only to other vertices in J i, and so any dominating set must contain at least one
6 Ars Math. Contemp. 24 (2024) #P3.04
vertex from each copy. Hence, n ≤ γ(Jn) ≤ i(Jn). Then, it suffices to note that the set
{a1, a2, . . . , an} is an independent dominating set, and hence i(Jn) ≤ n, leading to the
result.
Corollary 2.4. For any variant of dominating set considered in this paper, each copy must
have weight at least 1.
3 Upper domination
In this section, we will determine the upper domination number for flower snarks. We
begin by considering what weights are possible for copies in a minimal dominating set.
Lemma 3.1. Consider the graph Jn for n ≥ 3. If S is a minimal dominating set for Jn
then the weight of each copy is either 1, 2 or 3.
Proof. We know from Corollary 2.4 that each copy must have positive weight. Then sup-
pose that a copy J i has weight 4. It can be easily checked that S \{ai} is also a dominating
set, contradicting the assumption that S is minimal.
In the following lemma, we use the term i depends on j to imply that S ∩N [i] = {j}.
Note that since S is minimal, for every vertex in S there must be at least one other vertex
which depends on it.
Lemma 3.2. Consider the graph Jn for n ≥ 4, and a minimal dominating set S. If a copy
J i has weight 3 in S, then both adjacent copies J i−1 and J i+1 have weight 1 in S.
Proof. Suppose it is not the case, that is, J i has weight 3 and at least one of J i−1 and J i+1
has weight greater than 1. Since bi, ci and di are all equivalent in this framing, there are
only two cases to consider; if ai ∈ S and if ai ̸∈ S.
First, consider the case when ai ∈ S. Then there are two other vertices from J i also
in S. Without loss of generality, suppose bi ∈ S and ci ∈ S. This situation is shown
in Figure 3 part (a). Then, since S is minimal, the removal of ai does not result in a
dominating set. This is only possible if di depends on ai. Hence, di−1 ̸∈ S and di+1 ̸∈ S.
Then, consider bi. Since S is minimal, at least one of bi−1 and bi+1 must depend on bi.
Without loss of generality, suppose it is the former. This implies that both bi−1 ̸∈ S and
ai−1 ̸∈ S. Then, ci−1 ∈ S, or else copy Ji−1 has weight 0 which contradicts Lemma 3.1.
Then, since S is minimal, ci+1 must depend on ci, which implies that ci+1 ̸∈ S and
ai+1 ̸∈ S. Hence, from Lemma 3.1 copy J i+1 also has weight 1, contradicting the initial
assumption.
Second, consider the case when ai ̸∈ S. Then, S contains bi, ci, and di. Since S
is minimal and ai does not depend on bi, at least one of bi−1 or bi+1 must depend on
bi. Without loss of generality, suppose it is the former. This implies that both bi−1 ̸∈ S
and ai−1 ̸∈ S. We can make analogous arguments for ci and di. Clearly, the dependent
vertices can not all be from the same copy, or else that copy has weight 0. Hence, two of
the dependent vertices are in one copy and one is in the other; without loss of generality we
will assume that bi−1 is dependent on bi, ci−1 is dependent on ci, and di+1 is dependent on
di. Hence, J i−1 has weight 1, and so by assumption, J i+1 has weight 2, and bi+1 ∈ S and
ci+1 ∈ S. But then, by similar arguments, it must be the case that bi+2 depends on bi+1,
and ci+2 depends on ci+1, implying that J i+2 has weight 1, and di+2 ∈ S. This situation
is displayed in Figure 3 part (b). Finally, it can be seen from this figure that S \ {di} is a
dominating set, contradicting the initial assumption that S is minimal.
R. Burdett et al.: Variants of the domination number for flower snarks 7
a
b
c
d
(a)
a
b
c
d
(b)
Figure 3: The two situations described in the proof of Lemma 3.2.
Recalling that wSi is the number of copies to have weight i in S, Lemma 3.2 implies
the following.
Corollary 3.3. Consider the graph Jn for n ≥ 4. If S is a minimal dominating set for Jn
then wS1 ≥ wS3 , with equality occurring if and only if wS1 = wS3 = n2 .
We are now ready to prove the main result of this section.
Theorem 3.4. Consider a graph Jn for n ≥ 3. Then,
Γ(Jn) =
{
2n, if n is even,
2n− 1, if n is odd.
Proof. We use the first formulation for upper domination from [6] to confirm that Γ(J3) =
5. Then, suppose that S is a minimal dominating set for Jn, for n ≥ 4. From Lemma 3.1
we have wS0 = w
S
4 = 0. Hence, we have w
S
1 +w
S
2 +w
S
3 = n, and w
S
1 +2w
S
2 +3w
S
3 = |S|.
Combining these, we obtain |S| = 2n + wS3 − wS1 . From Corollary 3.3 we know that
wS1 ≥ wS3 , and the inequality is strict if n is odd. Hence, |S| ≤ 2n if n is even, and
|S| ≤ 2n− 1 if n is odd. Then we just need to obtain the corresponding lower bounds.
Suppose that n is even. It is easy to check that if we repeat the configuration displayed
in Figure 4 part (a) n/2 times, what results is a minimal dominating set with weight 2n.
Hence, if n is even, we have Γ(Jn) ≥ 2n. Then suppose that n is odd. Again, it is easy
to check that if we repeat the configuration displayed in Figure 4 part (a) (n− 1)/2 times,
and then use the configuration displayed in Figure 4 part (b) for the final copy, what results
is a minimal dominating set with weight 2n− 1. Hence, if n is odd, Γ(Jn) ≥ 2n− 1.
a
b
c
d
(a)
a
b
c
d
(b)
Figure 4: The configuration for upper domination which gives the desired lower bound for
Γ(Jn) for n ≥ 3. Part (a) can be repeated as many times as necessary. Then, if n is odd,
use part (b) to finish. The result is a minimal dominating set with weight 2n if n is even, or
weight 2n− 1 if n is odd.
8 Ars Math. Contemp. 24 (2024) #P3.04
4 Upper bounds by construction
In the upcoming sections, we will determine lower bounds for the 2-domination, total dom-
ination, connected domination, secure domination, and weak Roman domination numbers
of flower snarks. To obtain equality, we will require corresponding upper bounds, which
we provide here. We leave it as an exercise to the reader to verify that the configurations
given here satisfy the requirements of the various kinds of domination, and that they imply
the appropriate upper bounds for Theorem 1.6.
For 2-domination, the configuration shown in Figure 5 can be repeated as often as
necessary, truncating the final time to get the desired size.
a
b
c
d
Figure 5: The configuration for 2-domination which gives the desired upper bound for
γ2(Jn). The result is a 2-dominating set of weight ⌈ 5n3 ⌉ if n ̸= 1 mod 3, or weight ⌈
5n
3 ⌉+1
if n = 1 mod 3.
For total domination, the configuration shown in Figure 6 part (a) can be repeated as
often as necessary. Then the configurations in parts (b), (c) and (d) can be used to complete
the remaining copies.
a
b
c
d
(a)
a
b
c
d
(b)
a
b
c
d
(c)
a
b
c
d
(d)
Figure 6: The configuration for total domination which gives the desired upper bound for
γt(Jn) for n ≥ 3. Part (a) can be repeated as many times as necessary. If n = 0 mod 4
this is sufficient. If n = 1 mod 4, use (b) to finish. If n = 2 mod 4, use part (c) to finish.
If n = 3 mod 4, use part (d) to finish. The result is a total dominating set of weight ⌈ 3n2 ⌉
if n ̸= 2 mod 4, or weight 3n2 + 1 if n = 2 mod 4.
For connected domination, the configuration shown in Figure 7 can be repeated as often
as necessary, truncating the final time to get the desired size. If n ̸= 1 mod 4 the result is
connected dominating. If n = 1 mod 4, then removing d1 and adding b1 gives the desired
result.
For secure domination, the configuration shown in Figure 8 part (a) can be repeated as
often as necessary. Then the configurations in parts (b), (c), (d), and (e) can be used to com-
plete the remaining copies. Since secure domination is an upper bound for weak Roman
domination, these configurations also give an upper bound for weak Roman domination.
R. Burdett et al.: Variants of the domination number for flower snarks 9
a
b
c
d
Figure 7: The configuration for connected domination which gives the desired upper bound
for γc(Jn) for n ≥ 3. It may be repeated as many times as necessary, truncating the final
time to get the final size. If n = 1 mod 4, then in the first copy, remove d1 and add b1. The
result is a connected dominating set of weight 2n if n is even, or 2n− 1 if n is odd.
a
b
c
d
(a)
a
b
c
d
(c)
a
b
c
d
(d)
a
b
c
d
(b)
a
b
c
d
(e)
Figure 8: The configuration for secure domination which gives the desired upper bound for
γs(Jn) for n ≥ 4. Part (a) can be repeated as many times as necessary. If n = 0 mod 4,
use part (b) to finish. If n = 1 mod 4, use part (c) to finish. If n = 2 mod 4, use part (d) to
finish. If n = 3 mod 4, use part (e) to finish. In all cases, the result is a secure dominating
set of weight ⌈ 3n+12 ⌉.
5 2-domination
In this section, we will determine the 2-domination numbers for flower snarks.
Lemma 5.1. Consider the graph Jn for n ≥ 3, and a 2-dominating set S. If the copy J i
has weight 1 in S, then ai ∈ S.
Proof. Recall that ai is adjacent only to other vertices in J i. From the definition of 2-
domination, if ai ̸∈ S then it must have at least two neighbours in S. Since J i has weight
1, this is impossible, and so ai ∈ S.
Theorem 5.2. Consider the graph Jn for n ≥ 3, and a 2-dominating set S. Then any copy
with weight 1 in S has a neighbouring copy with weight 3 or 4 in S.
Proof. Without loss of generality, suppose that J2 has weight 1. Then, from Lemma 5.1
we have a2 ∈ S. Then, suppose that its neighbours J1 and J3 both have weight less than 3.
At this stage, vertices b2, c2 and d2 have only one neighbour in S, so they each need at least
one more. Without loss of generality, suppose that b1 ∈ S. Then, consider the case when
c1 ∈ S. Since J1 has weight less than 3, this implies that a1 ̸∈ S and d1 ̸∈ S. However,
it is then impossible for d1 to have two neighbours in S. This situation is displayed in part
(a) of Figure 9.
10 Ars Math. Contemp. 24 (2024) #P3.04
a
b
c
d
J1 J2
(a)
a
b
c
d
J1 J2 J3
(b)
Figure 9: The two situations described in the proof of Theorem 5.2. In part (a), d1 cannot
have two neighbours in S. In part (b), copy b3 cannot have two neighbours in S.
Hence, we must have c1 ̸∈ S. Then, c1 must have two neighbours in S, which implies
that a1 ∈ S. Since J1 has weight less than 3, this implies that d1 ̸∈ S. Then, in order for
c2 and d2 to have two neighbours in S, we must have c3 ∈ S and d3 ∈ S, respectively.
Since J3 has weight less than 3, this implies that a3 ̸∈ S and b3 ̸∈ S. However, it is
then impossible for b3 to have two neighbours in S, completing the proof. This situation is
displayed in part (b) of Figure 9.
We are now ready to prove the main result of this section.
Theorem 5.3. Consider the graph Jn for n ≥ 3. Then,
γ2(Jn) =
{⌈
5n
3
⌉
, if n ̸= 1 mod 3,
5n+4
3 , if n = 1 mod 3.
Proof. The upper bound was established in Section 4. Then, from Corollary 2.4 we know
that each copy has weight at least 1. This, combined with Theorem 5.2, implies that any
three set of consecutive copies have weight at least 5. Hence we have γ2(S) ≥ ⌈ 5n3 ⌉.
Hence, Theorem 5.3 is true for n ̸= 1 mod 3.
Suppose that n = 1 mod 3, and we have a 2-dominating set S such that |S| < 5n+43 .
Hence, we must have |S| = 5n+13 . For each copy J
i, denote by w3(i) the combined
weights of J i, J i+1, and J i+2, where the superscripts are taken modulo n. Recall that
w3(i) ≥ 5. Hence there must be a single value k such that w3(k) = 6 and w3(j) = 5 for
all j ̸= k. Consider the copies Jk, Jk+1, Jk+2. We will consider the possible patterns they
could have, and show that each is impossible. Since w3(k) has weight 6, the only possible
patterns (up to symmetry) for copies Jk, Jk+1 and Jk+2 are 123, 132, 222, and 312.
Suppose that Jk, Jk+1 and Jk+2 meet either the pattern 123 or the pattern 132. Since
w3(k + 1) = 5, this implies that Jk+3 has weight 0, which contradicts Corollary 2.4.
Suppose next that Jk, Jk+1 and Jk+2 meet the pattern 222. Since w3(k + 1) =
w3(k+2) = 5, this implies that Jk+3 has weight 1, and Jk+4 has weight 2. However, this
contradicts Theorem 5.2 since Jk+3 has no neighbour with weight 3 or 4. Hence, this is
impossible.
Finally, suppose that Jk, Jk+1 and Jk+2 meet pattern 312. Since w3(k+1) = w3(k+
2) = w3(k+3) = 5, this implies that Jk+3 has weight 2, Jk+4 has weight 1, and Jk+5 has
weight 2. Again, this contradicts Theorem 5.2 since Jk+4 has no neighbour with weight 3
or 4. Hence, all cases are impossible, and so |S| ≥ 5n+43 , completing the proof.
R. Burdett et al.: Variants of the domination number for flower snarks 11
6 Total domination
In this section, we will determine the total domination numbers for flower snarks. We begin
by identifying three patterns which cannot occur in total dominating sets of Jn.
Theorem 6.1. Consider the graph Jn for n ≥ 3, and a total dominating set S. Then S
does not contain the patterns 111, 1121, or 12121.
Proof. From Corollary 2.4, each copy of Jn has weight at least 1 in S. Also, if a copy J i
has weight 1, then ai ̸∈ S because otherwise ai itself is not dominated.
Suppose that S has the pattern 111. Without loss of generality, suppose the three copies
meeting this pattern are J1, J2, J3. As indicated above, a2 ̸∈ S. Regardless of which
vertex from J2 is in S, it does not dominate any of b2, c2, d2. Also, any vertex from J1
dominates at most one vertex from J2, and likewise for any vertex from J3. Hence there
is at least one vertex in J2 which is not dominated, contradicting the assumption that S is
a total dominating set.
Then, suppose that S has the pattern 1121. Without loss of generality, suppose the four
copies meeting this pattern are J1, J2, J3, J4. Using an equivalent argument to above, it
must be the case that b2, c2, d2 are dominated by one vertex from J1 and two vertices from
J3. Hence, a3 ̸∈ S. This means none of the vertices from J3 dominate any of b3, c3, d3.
Also, any vertex from J2 dominates at most one vertex from J3, and likewise for any vertex
from J4. Hence there is at least one vertex in J3 which is not dominated, contradicting the
assumption that S is a total dominating set.
Finally, suppose that S has the pattern 12121. Without loss of generality, suppose the
five copies meeting this pattern are J1, . . . , J5. Since J1 and J3 are both weight 1, they can
collectively dominate at most two vertices from J2. Hence, a2 ∈ S, and by an equivalent
argument, a4 ∈ S. Note that none of the vertices from J3 can dominate any of b3, c3
or d3. Also, the vertices from J2 dominate at most one vertex from J3, and likewise for
the vertices from J4. Hence there is at least one vertex in J3 which is not dominated,
contradicting the assumption that S is a total dominating set.
An immediate observation arising from Corollary 2.4 and Theorem 6.1 is that any four
consecutive copies must collectively have weight at least 6 in S, leading to the following
corollary.
Corollary 6.2. For n ≥ 4, γt(Jn) ≥
⌈
3n
2
⌉
.
We are now ready to prove the main result of this section.
Theorem 6.3. Consider the graph Jn for n ≥ 3. Then,
γt(Jn) =
{⌈
3n
2
⌉
, if n ̸= 2 mod 4,
3n
2 + 1, if n = 2 mod 4.
Proof. The upper bound was established in Section 4. We use the formulation for total
domination from [7] to confirm that γt(J3) = 5. Then, suppose there is some value k ≥
4 such that Theorem 6.3 is false. If k ̸= 2 mod 4 then we have γt(Jk) ≤
⌈
3k
2
⌉
− 1,
contradicting Corollary 6.2. Hence, we must have k = 2 mod 4. Hence, γt(Jk) ≤ 3k2 , and
from Corollary 6.2 this implies that γt(Jk) = 3k2 .
12 Ars Math. Contemp. 24 (2024) #P3.04
Suppose that we have a total dominating set S with weight 3k2 . Note that this implies
that every set of four consecutive copies of Jn has weight 6 in S; call this property 1. It
is clear that property 1 implies that no copy has weight 4 in S. If a copy has weight 3
in S, then in order to satisfy property 1, the next three copies must have weight 1, which
contradicts Theorem 6.1. Hence, every copy has weight 1 or 2 in S; call this property 2.
It can be easily checked that there are only two ways to satisfy properties 1 and 2 without
contradicting Theorem 6.1; either S contains the repeated pattern 1212 . . . 12, or S contains
the repeated pattern 11221122 . . . 1122. In the former case, S contains the pattern 12121
which by Theorem 6.1 is impossible. Hence, we must have the latter case. Also, the latter
case is impossible because k = 2 mod 4. Hence, all cases are impossible, completing the
proof.
7 Connected domination
In this section, we will determine the connected domination numbers for flower snarks.
The following three remarks are obvious, but we list them here to aid the readability of two
upcoming proofs.
Remark 7.1. Suppose that S is a connected dominating set for a graph G. If a new graph
H is created by either (a) adding an edge between two non-adjacent vertices in G, or (b)
deleting a vertex v ̸∈ S from G, then S is also a connected dominating set for H .
Remark 7.2. Suppose that S is a connected dominating set for a graph G, and that G
contains a degree 1 vertex v ∈ S whose neighbour has degree larger than 1. If a new graph
H is created by deleting v from G, then S \ {v} is a connected dominating set for H .
Remark 7.3. Suppose that S is a connected dominating set for a graph G, and that G
contains a triangle uvw such that v is degree 2, and v ∈ S. If a new graph H is created by
deleting v from G, then S \ {v} is a connected dominating set for H .
In the following, we define V S(J i) := S ∩ (ai, bi, ci, di), that is, V S(J i) is the set of
vertices from J i that are contained in S.
Theorem 7.4. Consider the graph Jn for n ≥ 4, and let S be a connected dominating set
for Jn. Suppose that there is a copy J i such that either ai ̸∈ S, or J i has weight 2 in S.
Then S := S \ V S(J i) is a connected dominating set for Jn−1.
Proof. Consider first the situation when ai ̸∈ S, and consider the graph Jn−1. One may
think of Jn−1 as being constructed by starting with Jn and then “smoothing out” copy J i,
in the following sense. First, we add edges connecting bi−1 to bi+1, ci−1 to ci+1 and di−1
to di+1, and then we delete the vertex set V (J i). Suppose that we are midway through this
process, having added all three edges, and having deleted ai. Call this intermediate graph
G, and note from Remark 7.1 that S is a connected dominating set for G. Then, note that in
G, bi is a degree 2 vertex and is part of a triangle bi−1bibi+1. Now, suppose that we delete
bi from G, to obtain a new intermediate graph G2. If bi ̸∈ S then from Remark 7.1 we can
see that S is a connected dominating set for G2. If bi ∈ S then from Remark 7.3 we can
see that S \ {bi} is a connected dominating set for G2. Applying analogous arguments for
ci and di, we obtain the result. The graphs G and G2 are displayed in Figure 10.
We next consider the situation when J i has weight 2 in S. If ai ̸∈ S then the previous
paragraph applies. If ai ∈ S then there must be one more vertex from J i also in S; without
R. Burdett et al.: Variants of the domination number for flower snarks 13
loss of generality, suppose that bi ∈ S. Again, we construct Jn−1 by adding edges to
and deleting vertices from Jn. Suppose that we are midway through this process, having
added all three edges, and having deleted ci and di. Call this intermediate graph G3. From
Remark 7.1 we know that S is a connected dominating set for G3. Note that in G3, ai is a
degree 1 vertex. Remark 7.2 implies that we can obtain a second intermediate graph, G4,
by deleting ai, and that S \ {ai} is a connected dominating set for G4. Finally, note that in
G4, bi is degree 2 vertex and is part of a triangle bi−1bibi+1. Hence, Remark 7.3 implies
the result. The graphs G3 and G4 are displayed in Figure 10.
a
b
c
d
G
a
b
c
d
G2
a
b
c
d
G3
a
b
c
d
G4
Figure 10: Sections of the four intermediate graphs G, G2, G3, G4 from the proof of
Theorem 7.4.
We also make use of the concept of “smoothing out” a copy in the following lemma.
Lemma 7.5. Consider the graph Jn for n ≥ 4, and let S be a connected dominating set
for Jn. Suppose that there is a copy J i with weight 4 in S. Then for any positive integer
k ≤ n−3, we have that S := S \(V S(J i+1)∪ . . .∪V S(J i+k)) is a connected dominating
set for Jn−k.
Proof. Suppose that we delete from Jn all vertices from each of the copies J i+1, . . . , J i+k.
Call this intermediate graph G. Then, we add edges connecting bi to bi+k+1, ci to ci+k+1
and di to di+k+1, and call the resulting graph G2. Since we can always relabel the vertices
so that the twist occurs elsewhere in the graph, it can then be seen that G2 is isomorphic to
Jn−k. Both G and G2 are displayed in Figure 11. Since bi ∈ S, ci ∈ S, and di ∈ S, it
is clear that vertices bi+k+1, ci+k+1 and di+k+1 are dominated in G2. Also, from Corol-
lary 2.4 we know that J i+k+1 has weight at least 1, and so ai+k+1 is dominated. Hence,
S is a dominating set for G2. Next, we need to show that S is a connected dominating
set for G2. Recall the intermediate graph G. It is clear that the subgraph of G induced by
S is either connected, or has exactly two connected components. In the former case, the
subgraph of G2 induced by S is also connected. In the latter case, it is clear that there must
be an edge vw in G2 such that v ∈ J i, w ∈ J i+k+1 and both v, w are contained in S, and
hence the subgraph of G2 induced by S is connected. Either way, we obtain the desired
result.
Lemma 7.6. Suppose that there is an odd value n ≥ 5 such that γc(Jn−1) = 2n− 2. If S
is a connected dominating set for Jn such that |S| = 2n− 1, then wS4 is even.
Proof. Suppose that wS2 > 0. Then there is a copy J
i with weight 2. From Theorem 7.4,
we can obtain a connected dominating set for Jn−1 of cardinality 2n− 3, contradicting the
initial assumption. Hence, wS2 = 0. Then, we have w
S
1 +w
S
3 +w
S
4 = n, and w
S
1 +3w
S
3 +
4wS4 = 2n− 1. Combining these two, we obtain 3wS4 = n− 1− 2wS3 . Since n is odd, this
implies that wS4 is even.
14 Ars Math. Contemp. 24 (2024) #P3.04
a
b
c
d
J i . . . J i+k+1
G
a
b
c
d
J i . . . J i+k+1
G2
Figure 11: Sections of the two intermediate graphs G and G2 from the proof of Lemma 7.5.
Theorem 7.7. Consider the graph Jn for n ≥ 3, and suppose that S is a connected
dominating set. Then S does not contain the patterns 111 or 1312131.
Proof. Any connected dominating set with |S| ≥ 2 is also a total dominating set, and hence
the result for pattern 111 follows immediately from Theorem 6.1.
Next, consider the case when S contains the pattern 1312131. Without loss of gener-
ality, suppose the copies meeting this pattern are J1, . . . , J7. Suppose that a4 ̸∈ S. Then,
without loss of generality, suppose that b4 ∈ S, c4 ∈ S, and d4 ̸∈ S. This situation is
displayed in part (a) of Figure 12. Since S is dominating, it must contain at least one of d3
and d5. Since both J3 and J5 have weight 1, both options are equivalent, so without loss
of generality we will assume that d5 ∈ S. Then a5 ̸∈ S, b5 ̸∈ S, and c5 ̸∈ S. In order for
S to be connected, we must have b3 ∈ S and c3 ∈ S, but this is impossible since J3 has
weight 1. Hence, it must be the case that a4 ∈ S.
Again, without loss of generality, suppose that b4 ∈ S, c4 ̸∈ S and d4 ̸∈ S. This
situation is displayed in part (b) of Figure 12. Since S is connected, it must contain at least
one b3 or b5. As in the previous paragraph, without loss of generality we will assume that
b5 ∈ S. Then, in order for S to be dominating, we must have c6 ∈ S and d6 ∈ S. Now,
suppose that b6 ∈ S. Then, since S is connected, it must contain both c7 and d7, but this
is impossible since J7 has weight 1. Hence, it must be the case that b6 ̸∈ S, and hence
a6 ∈ S. Then, since S is connected, we must have b3 ∈ S and b2 ∈ S. In order for S to be
dominating, we must have c2 ∈ S and d2 ∈ S, and since J2 has weight 3 this implies that
a2 ̸∈ S. Finally, to ensure S is connected, it must contain each of b1, c1 and d1, but this is
impossible since J1 has weight 1.
a
b
c
d
J3 J4 J5
1 2 1
(a)
a
b
c
d
J1 J2 J3 J4 J5 J6 J7
1 3 1 2 1 3 1
(b)
Figure 12: The two situations described in the proof of Theorem 7.7. In part (a), J3 has
too many vertices in S. In part (b), J1 has too many vertices in S.
R. Burdett et al.: Variants of the domination number for flower snarks 15
Theorem 7.8. Consider the graph Jn for even n ≥ 6, and a connected dominating set S
for Jn such that |S| = 2n−1. If γc(Jn−1) = 2n−3, and wS4 = 0, then S does not contain
the pattern 112.
Proof. Without loss of generality, suppose that one set of copies meeting the pattern 112
is J2, J3, J4, and consider also J1 and J5. Since J2 and J3 have weight 1, we know that
a2 ̸∈ S and a3 ̸∈ S. Without loss of generality, suppose that b2 ∈ S. Then, suppose that
b3 ∈ S as well. This situation is displayed in part (a) of Figure 13. Since S is dominating,
it must also contain each of c1, d1, c4, and d4. Since J4 has weight 2, we have a4 ̸∈ S
and b4 ̸∈ S. Since S is connected, it implies that b1 ∈ S. Since there are no copies of
weight 4 in S, this implies that a1 ̸∈ S. However, by Theorem 7.4, we can then obtain a
connected dominating set for Jn−1 of cardinality 2n−4, contradicting the assumption that
γc(Jn−1) = 2n− 3. Hence, the assumption that b3 ∈ S must be false.
We instead have b2 ∈ S and b3 ̸∈ S. Without loss of generality, suppose that c3 ∈ S.
This situation is displayed in part (b) of Figure 13. Since S is dominating, it must also
contain d4. Since S is connected, we have c4 ∈ S, and since J4 has weight 2, we have
a4 ̸∈ S and b4 ̸∈ S. Then, since S is dominating, we have b5 ∈ S, and since S is connected
we have c5 ∈ S and d5 ∈ S. Since there are no copies of weight 4 in S, it implies that
a5 ̸∈ S. However, by Theorem 7.4, we can the obtain a connected dominating set for Jn−1
of cardinality 2n − 4, which again contradicts the assumption that γc(Jn−1) = 2n − 3,
completing the proof.
a
b
c
d
J1 J2 J3 J4 J5
1 1 2
(a)
a
b
c
d
J1 J2 J3 J4 J5
1 1 2
(b)
Figure 13: The two situations described in the proof of Theorem 7.8. In both parts, there is
a copy with weight 3, but with the a vertex not contained in S.
In the next theorem, we will require the following concept. Suppose that we have a
connected dominating set S for Jn. Denote by Jn(S) the subgraph of Jn induced by S. By
definition, Jn(S) is connected. Then, consider a set of consecutive copies J i, . . . , J i+k,
and define S = S ∩ (V (J i) ∪ . . . ∪ V (J i+k)). If Jn(S) is a disconnected graph, then we
say that the copies J i, . . . , J i+k are locally disconnected in S. Since S itself is connected,
it is clear that if S contain two sets of locally disconnected consecutive copies, they must
overlap by two or more copies.
Theorem 7.9. Consider the graph Jn for even n ≥ 6, and a connected dominating set S
for Jn such that |S| = 2n − 1. If γc(Jn−1) = 2n − 3, then any set of consecutive copies
meeting the patterns 113 or 3123 are locally disconnected.
Proof. Consider first the pattern 113. Without loss of generality, suppose that one set of
copies meeting this pattern is J1, J2, J3, and that this set of copies is not locally discon-
nected. Suppose that a3 ̸∈ S. Then, from Theorem 7.4 there exists a connected dom-
inating set for Jn−1 with cardinality 2n − 4, which is impossible since by assumption
16 Ars Math. Contemp. 24 (2024) #P3.04
γc(Jn−1) = 2n−3. Hence, a3 ∈ S. Then, without loss of generality, suppose that b3 ∈ S,
c3 ∈ S, and d3 ̸∈ S. This situation is displayed in part (a) of Figure 14. Since J2 has
weight 1, it is clear that a2 ̸∈ S. Then, in order for S to be dominating, it must contain at
least one of d1 and d2. However, if d2 ∈ S, then S does not contain b2 or c2, and hence
J1, J2, J3 are locally disconnected, contradicting the initial assumption. Hence, d2 ̸∈ S,
and so d1 ∈ S. But then, because J1 has weight 1, S does not contain a1, b1, or c1, which
again implies that J1, J2, J3 are locally disconnected, contradicting the initial assumption.
Hence, the initial assumption must be false, and J1, J2, J3 are locally disconnected.
Next, consider the pattern 3123. Without loss of generality, suppose that one set of
copies meeting this pattern is J1, J2, J3, J4, and that this set of copies if not locally dis-
connected. Using an identical argument as from the previous paragraph, we must have
a1 ∈ S and a4 ∈ S. Then, without loss of generality, suppose that b1 ∈ S and c1 ∈ S.
This situation is displayed in part (b) of Figure 14. Since J2 has weight 1, and the set
of copies is not locally disconnected, we have a2 ̸∈ S and d2 ̸∈ S. The remaining two
choices are equivalent; without loss of generality, suppose that b2 ∈ S. Then, since S
is dominating, and the set of copies is not locally disconnected, we must have b3 ∈ S
and d3 ∈ S. Finally, since S is dominating, and the set of copies is not locally discon-
nected, we must have b4 ∈ S, c4 ∈ S and d4 ∈ S. However, this is impossible since J4
has weight 3. Hence, the initial assumption must be false, and J1, J2, J3, J4 are locally
disconnected.
a
b
c
d
J1 J2 J3
1 1 3
(a)
a
b
c
d
J1 J2 J3 J4
3 1 2 3
(b)
Figure 14: The two situations described in the proof of Theorem 7.9. In part (a), the copies
are locally disconnected. In part (b), copy J4 has too many vertices in S.
Theorem 7.7, along with the fact that the patterns 113 and 3123 overlap by at most one
copy, leads to the following corollary.
Corollary 7.10. Consider the graph Jn for even n ≥ 6, and a connected dominating set S
for Jn such that |S| = 2n− 1. If γc(Jn−1) = 2n− 3, then S contains at most one instance
the patterns 113 or 3123.
We are finally ready to prove the main result of this section.
Theorem 7.11. Consider the graph Jn for n ≥ 3. Then,
γc(Jn) =
{
2n, if n is even,
2n− 1, if n is odd.
Proof. The upper bounds are provided in Section 4. We use the MTZ formulation for
connected domination from [10] to confirm that γc(J3) = 5, γc(J4) = 8, γc(J5) = 9,
R. Burdett et al.: Variants of the domination number for flower snarks 17
and γc(J6) = 12. Suppose there is some value k ≥ 7 such that Theorem 7.11 is true for
n = 3, . . . , k − 1, but false for n = k. We will first consider the case when k is odd.
Then there is a connected dominating set S for Jk such that |S| = 2k − 2. Clearly, S
contains a copy, say J i, with weight 1, and ai ̸∈ S. Then from Theorem 7.4, it implies that
there is a connected dominating set for Jk−1 with cardinality 2k− 3, which contradicts the
assumption that Theorem 7.11 is true for Jk−1.
Hence, k must be even. Then, there is a connected dominating set S for Jk such that
|S| = 2k − 1. Suppose that there are two copies of Jk with weight 2 in S. Then, from
Theorem 7.4 we can obtain a connected dominating set for Jk−2 with cardinality 2k − 5,
which contradicts the initial assumption. Hence, there must be at most one copy of Jk with
weight 2 in S. That is, either wS2 = 0 or w
S
2 = 1.
Suppose that wS2 = 0. Then we have w
S
1 +w
S
3 +w
S
4 = k, and w
S
1 +3w
S
3 +4w
S
4 = 2k−1.
From the latter equation, it is clear that wS1 and w
S
3 must have different parity. Hence,
from the former equation, wS4 must be odd. Combining the two equations, we obtain
2wS1 = k + 1 + w
S
4 . Note that this implies that more than half of the copies have weight
1 in S. From Theorem 7.7, S cannot contain the pattern 111. Hence, it can be seen that S
contains the pattern 11 at least wS4 +1 times. From Corollary 7.10 we know there is at most
one instance of the pattern 113 in S. Hence, there is at least wS4 instances of the pattern 11
where both adjacent copies have weight 4, which is impossible.
Hence, we must have wS2 = 1. Then, we have w
S
1 +w
S
3 +w
S
4 = k−1, and wS1 +3wS3 +
4wS4 = 2k − 3. From the latter equation, it is clear that wS1 and wS3 must have different
parity. Hence, from the former equation, wS4 must be even. Combining the two equations,
we obtain 2wS1 = k + w
S
4 . Similar to before, this implies that at least half of the copies
have weight 1 in S. From Theorem 7.7, S cannot contain the pattern 111. Hence, it can
be seen that S contains the pattern 11 at least wS4 times. Now, suppose that S contains the
pattern 4114. From Lemma 7.5, we can then obtain a connected dominating set for Jk−3
with cardinality 2k−7 which has one fewer copy of weight 4 than S, which in turn violates
Lemma 7.6. Hence, every instance of the pattern 11 has a copy of weight 2 or 3 next to it,
and from Corollary 7.10 this means there is at most one instance of the pattern 11. This,
in turn, implies that wS4 ≤ 1, and since wS4 is even, we have wS4 = 0. Hence, wS1 = k2 . If
there are no instances of the pattern 11, then S must contain the pattern 1312131, violating
Theorem 7.7. Hence there is exactly one instance of the pattern 11. This means that there
must be one other instance in S of two consecutive copies having non-unit weight. The
only options are that S contains the pattern 23, or the pattern 33.
Suppose S contains the pattern 23. Without loss of generality, suppose that the copies
J3, J4 meet this pattern. Since this is the only instance of S having two consecutive copies
of weight other than 1, we know that J2 has weight 1. From Theorem 7.8 we know that J1
cannot have weight 1, or else S would contain the pattern 112. The only remaining option
is that J1 has weight 3, and so copies J1, J2, J3, J4 meet the pattern 3123. Then, since
J3 has weight 2 and wS2 = 1, there are no other copies with weight 2. Hence, the one
instance of the pattern 11 which occurs elsewhere in the graph must be followed by a copy
of weight 3. That is, S contains both the patterns 113 and 3123, which from Corollary 7.10
is impossible. Therefore, S must not contain the pattern 23, and instead contains the pattern
33.
Finally, without loss of generality, suppose that the copies J1, J2 meet the pattern 33.
There is one vertex from J1 which is not contained in S. Suppose we define S2 which is
equal to the union of S and this one vertex. Hence, S2 is a connected dominating set for Jk
18 Ars Math. Contemp. 24 (2024) #P3.04
with cardinality 2k. Then, from Lemma 7.5, we can obtain a connected dominating set for
Jk−1 with cardinality 2k−3, which contains exactly one copy with weight 4, contradicting
Lemma 7.6.
Hence, in all cases a contradiction is reached, completing the proof.
8 Weak Roman domination and secure domination
In this section, we determine (simultaneously) the weak Roman domination numbers and
the secure domination numbers for flower snarks. Recall that for the weak Roman domina-
tion number, rather than seeking to construct a set S, we instead look to define a function
f : V → {0, 1, 2}. In order to use language consistent with the rest of this paper, in this
section we define the weight of a copy J i to be equal to f(ai) + f(bi) + f(ci) + f(di).
Note that this is somewhat more ambiguous than in previous sections; for instance, if a
copy has weight 2, it may have two vertices with weight 1, or a single vertex with weight
2. We will deal with these ambiguities when they arise. Similarly to in previous sections,
we will say that f contains a pattern if there is a set of consecutive copies whose weights
meet that pattern.
Although there is a technical definition for weak Roman domination (e.g. see Defini-
tion 1.4), it is useful to provide an intuitive interpretation. Recall that for standard domina-
tion, one interpretation is that the set of vertices needs to be protected. If a guard is placed
at a vertex, then it protects that vertex, and also all adjacent vertices. A configuration of
guards which protects all vertices corresponds to a dominating set. A similar interpreta-
tion applies for weak Roman domination. Suppose that at each vertex we can place up to
two guards. As before, a vertex is protected if there is at least one guard there, or there is
at least one guard among its adjacent vertices. Then we further consider the notion of a
vertex being defended. We say a vertex v is defended if there is at least one guard at v, or
alternatively, if it possible to relocate one guard from an adjacent vertex w to v, in such a
way that all vertices are still protected by the resulting configuration of guards. In the latter
case, we will say that w can defend v. Then a weak Roman dominating function is one in
which every vertex is defended.
Throughout this section, we will often use an argument which goes as follows; suppose
there is exactly one guard at v, and that v defends another adjacent vertex w. In order to
do so, the guard from v would move to w. However, doing so may mean another vertex u,
also adjacent to v, becomes unprotected. In such a case, we will say that v cannot defend
w without leaving u unprotected. Another alternative is as follows; suppose again that v
defends w. In order to do so, the guard from v would move to w. However, doing so may
mean that u will be unprotected unless there is a guard at another vertex, say x. In such a
case, we will say in order for v to defend w, there must be a guard at x to avoid leaving u
unprotected.
Although the following result is simple, we include it here as it will be used many times
in this section.
Lemma 8.1. Consider the graph Jn, for n ≥ 3, and a weak Roman dominating function
f . If a copy J i has weight 1 in f , then none of the vertices from J i can defend any vertices
from J i−1 or J i+1.
Proof. Since J i has weight 1, there is exactly one vertex with positive weight. If f(ai) = 1,
then the result follows immediately since ai is not adjacent to any vertices from J i−1
R. Burdett et al.: Variants of the domination number for flower snarks 19
or J i+1. Then, suppose instead that f(ai) = 0 and one of the other vertices in J i has
weight 1. Then that vertex cannot defend any vertex from J i−1 or J i+1 without leaving ai
unprotected.
Theorem 8.2. Consider the graph Jn, for n ≥ 3, and a weak Roman dominating function
f . Then f does not contain the patterns 111, 1121 or 1212121.
Proof. Suppose that f contains the pattern 111. Without loss of generality, suppose that
copies J1, J2, J3 meet the pattern 111 in f . This situation is displayed in part (a) of
Figure 15. Each vertex in J2 must be defended, but since J1 and J3 have weight 1, from
Lemma 8.1 none of their vertices can defend any vertices from J2. Hence, each vertex in
J2 must be defended solely by vertices in J2. It is clear that this implies that f(a2) = 1.
Then, consider b2. In order for a2 to defend b2, there must be a guard at either c1 or c3 to
avoid leaving c2 unprotected. Likewise, in order for a2 to defend b2, there must be a guard
at either d1 or d3 to avoid leaving d2 unprotected. Since J1 and J3 have weight 1, at most
one vertex from each can have a guard. Without loss of generality, suppose that f(c1) = 1
and f(d3) = 1. Then a2 cannot defend c2 without leaving b2 unprotected. Hence, this is
impossible, and f does not contain the pattern 111.
Next, suppose that f contains the pattern 1121. Without loss of generality, suppose that
copies J1, J2, J3, J4 meet the pattern 1121 in f . Since J2 and J4 have weight 1, from
Lemma 8.1 none of their vertices can defend any vertices from J3. Hence, each vertex
from J3 must be defended solely by vertices in J3. Clearly, this implies that f(a3) ≥ 1.
There are two possibilities, either f(a3) = 2, or f(a3) = 1 and there is a guard at another
vertex in J3. Suppose first that f(a3) = 2. Then there are no vertices from J1 or J3
that can defend any vertices from J2. Hence, J2 is in an equivalent situation to J2 in the
previous paragraph and so this situation is impossible. Instead, suppose that f(a3) = 1
and, without loss of generality, that f(b3) = 1. This situation is displayed in part (b) of
Figure 15. Clearly, vertices c2 and d2 can only be defended by vertices from J2, and hence
we must have f(a2) = 1. Then, in order for a2 to defend c2, there must be a guard at d1 to
avoid leaving d2 unprotected. Similarly, in order for a2 to defend d2, there must be a guard
at c1 to avoid leaving c2 unprotected. This is impossible since J1 has weight 1, and so f
does not contain the pattern 1121.
a
b
c
d
J1 J2 J3
1 1 1
(a)
a
b
c
d
J1 J2 J3 J4
1 1 2 1
(b)
Figure 15: The first two situations described in the proof of Theorem 8.2. In part (a), a2
cannot defend c2 without leaving b2 unprotected. In part (b), there are too many guards in
J1.
Finally, suppose that f contains the pattern 1212121. Without loss of generality, sup-
pose that copies J1, . . . , J7 meet the pattern 1212121 in f . Since J1 and J3 have weight
1, from Lemma 8.1 none of their vertices can defend any vertices from J2. Hence, each
vertex from J2 must be defended solely by vertices in J2, which implies that f(a2) ≥ 1.
20 Ars Math. Contemp. 24 (2024) #P3.04
Analogous arguments imply that f(a4) ≥ 1 and f(a6) ≥ 1. Now, consider J2. There are
two possibilities, either f(a2) = 2, or f(a2) = 1 and there is a guard at another vertex
in J2. Suppose first that f(a2) = 2. Then there are no vertices from J2 that can defend
any vertices from J3, and at most one vertex from J4 can defend a vertex from J3. Hence,
J3 is in an equivalent situation to J2 in the previous paragraph, and so this situation is
impossible.
Instead, suppose that f(a2) = 1 and, without loss of generality, that f(b2) = 1. This
situation is displayed in Figure 16. Then, in order for a2 to defend c2, there must be a
guard at either d1 or d3 to avoid leaving d2 unprotected. Similarly, in order for a2 to defend
d2, there must be a guard at either c1 or c3 to avoid leaving c2 unprotected. Since J1
and J3 have weight 1, at most one vertex from each may have a guard. Without loss of
generality, suppose that f(c1) = 1 and f(d3) = 1. Then, since f is dominating, we must
have f(c4) = 1 in order to protect c3. Now, in order for a4 to defend d4, there must be
a guard at b5 to avoid leaving b4 unprotected. Then, since f is dominating, we must have
f(d6) = 1 in order to protect d5. Finally, consider vertex c5. There is only one adjacent
vertex with a guard that can defend it, c4. However, c4 cannot defend c5 without leaving
c3 unprotected. Thus, c5 is not defended. This is impossible, and hence f does not contain
the pattern 1212121.
a
b
c
d
J1 J2 J3 J4 J5 J6 J7
1 2 1 2 1 2 1
Figure 16: The third situation described in the proof of Theorem 8.2. Here, c4 cannot
defend c5 without leaving c3 unprotected.
Lemma 8.3. Consider the graph Jn, for n ≥ 4, and a weak Roman dominating function f
with weight w(f) ≤ 3n2 . Then any set of four consecutive copies have a combined weight
of 6 in f , every copy has weight either 1 or 2 in f , and w(f) = 3n2 .
Proof. Denote by w4(i) the combined weights of J i, J i+1, J i+2, J i+3 where the super-
scripts are taken modulo n. Now, by Corollary 2.4 we know that no copies have weight
0, and so w4(i) ≥ 4. Suppose w4(i) = 4. This implies that J i, J i+1, J i+2, J i+3 all
have weight 1. However, this means f contains the pattern 111, which by Theorem 8.2 is
impossible. Then, suppose w4(i) = 5. Up to symmetry, there are only two possibilities;
copies J i, J i+1, J i+2, J i+3 either have the pattern 1112 or 1121. Both of these options are
impossible by Theorem 8.2. Hence, we have w4(i) ≥ 6. Then, by assumption, we have∑n
i=1 w
4(i) ≤ 6n. This is only possible if all w4(i) = 6, and also implies that w(f) = 3n2 .
Since each copy has weight at least one, and each set of four consecutive copies has a
combined weight of six, it is clear that any individual copy must have weight at most three.
Suppose there is a copy J i with weight 3 in f , then the next three copies must each have
weight 1. However, by Theorem 8.2 this is impossible. Hence, each copy J i must have
weight either 1 or 2 in f .
R. Burdett et al.: Variants of the domination number for flower snarks 21
Lemma 8.4. Consider the graph Jn, for n ≥ 3, and a weak Roman dominating func-
tion f with weight w(f). Suppose there is an integer k ≥ 3 such that in f , the config-
uration of guards in copies J i+1, . . . , J i+k is identical to the configuration of guards in
J i+k+1, . . . , J i+2k, and suppose that J i+1, . . . , J i+k collectively contain g guards. Then
there is a weak Roman dominating function for Jn−k with weight equal to w(f)− g.
Proof. Suppose that we “smooth out” copies J i+1, . . . , J i+k in the way displayed in Fig-
ure 11. That is, we add edges connecting bi to bi+k+1, ci to ci+k+1, and di to di+k+1,
and then we delete the copies J i+1, . . . , J i+k. Call the resulting graph G2. It is easy to
check that G2 is isomorphic to Jn−k. Then, define a new function f2 such that f2(v) =
f(v) if v ∈ V \ {V (J i+1) ∪ . . . ∪ V (J i+k)}, and f2(v) is undefined otherwise. Since
J i+1, . . . , J i+k collectively contain g guards in f , it is clear that w(f2) = w(f)− g. Then
if we can show that f2 is a weak Roman dominating function for G2, the result follows
immediately.
For a given function, one can check to see if a vertex v is defended by observing the
configuration of guards in vertices no more than distance three away from v. Then, for
any vertex v in G2, consider the configuration of graphs (according to f2) in the subgraph
induced by the vertices at most distance 3 from v. By assumption, this is identical to the
corresponding configuration of guards (according to f ) in the subgraph induced by the
vertices at most distance 3 from v in Jn. Hence, all vertices of G are defended in f2, and
so f2 is a weak Roman dominating function for G, leading to the desired result.
In the proof of the following theorem, whenever there are two guards at a vertex, we
will mark that vertex with a .
Theorem 8.5. Consider the graph Jn, for n ≥ 9, and a weak Roman dominating function
f . If f contains the pattern 21122112, then there exists a weak Roman dominating function
for Jn−4 with weight equal to w(f)− 6.
Proof. Without loss of generality, suppose that copies J1, . . . , J8 meet the pattern
21122112 in f . Consider copy J4, and suppose that f(a4) = 2. This situation is dis-
played in part (a) of Figure 17. Then, no vertices from J4 can defend any vertices from
J3, and by Lemma 8.1 the same is also true for J2. Hence, all four vertices in J3 must be
defended by vertices in J3. This implies that f(a3) = 1. Then, in order for a3 to defend
b3, there must be a guard at c2 to avoid leaving c3 unprotected, and there must also be a
guard at d2 to avoid leaving d3 unprotected. Since J2 has weight 1, this is impossible, and
so f(a4) ̸= 2.
Then, suppose that f(a4) = 1. Then there is another vertex in J4 with a guard. With-
out loss of generality, suppose that f(b4) = 1. This situation is displayed in part (b) of
Figure 17. Using a similar argument as in the previous paragraph, vertices c3 and d3 must
be defended by vertices from J3, and hence f(a3) = 1. Then, in order for a3 to defend c3,
there must be a guard at d2 to avoid leaving d3 unprotected. Likewise, in order for a3 to
defend d3, there must be a guard at c2 to avoid leaving c3 unprotected. Since J2 has weight
1, this is impossible. Hence we can conclude that f(a4) = 0. It is clear that identical
arguments can be made to conclude that f(a1) = f(a5) = f(a8) = 0 as well.
Then, suppose that there is a vertex in J4 with two guards. Without loss of generality,
suppose that f(b4) = 2. This situation is displayed in part (c) of Figure 17. An identical
argument to that in the previous paragraph can be used to show that f(a3) = 1, and this
again implies that f(c2) = f(d2) = 1. Since J2 has weight 1, this is impossible. Hence,
22 Ars Math. Contemp. 24 (2024) #P3.04
exactly two vertices in J4 have weight 1. Again, identical arguments can be made to reach
the same conclusion for each of J1, J5 and J8.
Now, without loss of generality, suppose that f(b4) = f(c4) = 1. Then, d4 must be
defended by either d3 or d5, and by Lemma 8.1 it cannot be d3. Hence, we must have
f(d5) = 1, and there must be one more vertex in J5 with a guard, either b5 or c5. Due to
symmetry, either choice may be made without loss of generality; we will choose f(b5) = 1.
Now, consider vertex d3. From Lemma 8.1 it cannot be defended by d2. Hence, we must
have either f(a3) = 1 or f(d3) = 1.
Suppose that f(a3) = 1. Then, c3 must be defended by at least one of a3 or c4 (from
Lemma 8.1 it cannot be defended by c2). Suppose first that a3 defends c3. This situation is
displayed in part (d) of Figure 17. In order for a3 to defend c3, there must be a guard at d2
to avoid leaving d3 unprotected. Then, in order to defend b2 and c2 we must have f(b1) = 1
and f(c1) = 1 respectively. But then, b1 cannot defend a1 without leaving b2 unprotected,
and c1 cannot defend a1 without leaving c2 unprotected. Hence, a1 is not defended, which
is impossible, and so we conclude that a3 cannot defend c3. Hence, c4 must defend c3.
This situation is displayed in part (e) of Figure 17. In order for c4 to defend c3, there must
be a guard at c6 to avoid leaving c5 unprotected. Also, the only vertex which can defend
d4 is d5, but in order to do so, there must be a guard at d7 to avoid leaving d6 unprotected.
Finally, consider a5, which can only be defended by either b5 or d5. However, b5 cannot
defend a5 without leaving b6 unprotected, and d5 cannot defend a5 without leaving d4
unprotected. Hence, all of these cases are impossible, and so conclude that f(a3) = 0, and
accordingly, f(d3) = 1.
The current situation is displayed in part (f) of Figure 17. Now consider c3. From
Lemma 8.1 it is clear that c2 cannot defend c3, so c4 must defend c3. In order for c4 to
defend c3, there must be a guard at c6 to avoid leaving c5 unprotected. Likewise, from
Lemma 8.1, d3 cannot defend d4, so d5 must defend d4. In order for d5 to defend d4, there
must be a guard at d7 to avoid leaving d6 unprotected. Furthermore, from Lemma 8.1, c6
cannot defend c5, so c4 must defend c5. In order for c4 to defend c5, there must be a guard
at c2 to avoid leaving c3 unprotected. Finally, from Lemma 8.1, the only vertices which
can defend b2 and d2 are b1 and d1 respectively, and so f(b1) = f(d1) = 1. Likewise,
from Lemma 8.1, the only vertices which can defend b7 and c7 are b8 and c8 respectively,
so f(b8) = f(c8) = 1.
At this point, it can be seen that the configuration of guards in J1, J2, J3, J4 is identical
to the configuration of guards in J5, J6, J7, J8. Then, the result follows immediately from
Lemma 8.4.
We are finally ready to prove the main result of this section.
Theorem 8.6. Consider the graph Jn, for n ≥ 3. Then, γs(Jn) = γr(Jn) =
⌈
3n+ 1
2
⌉
.
Proof. The (coincident) upper bounds for both weak Roman domination and secure dom-
ination are provided in Section 4. Note that γr(Jn) ≤ γs(Jn), so a corresponding lower
bound for weak Roman domination will also serve as a lower bound for secure domination.
We use the formulation for weak Roman domination from [7] to confirm that γr(J3) = 5,
γr(J4) = 7, γr(J5) = 8, γr(J6) = 10, γr(J7) = 11, and γr(J8) = 13, and the formu-
lation from [5] to confirm the corresponding results for secure domination. Then, suppose
there is a value k ≥ 9 such that Theorem 8.6 is true for n = 3, . . . , k − 1, but is not
true for n = k. That is, there exists a weak Roman dominating function f for Jk with
R. Burdett et al.: Variants of the domination number for flower snarks 23
a
b
c
d
J2 J3 J4
1 1 2
(a)
a
b
c
d
J1 J2 J3 J4 J5
2 1 1 2 2
(d)
a
b
c
d
J2 J3 J4
1 1 2
(b)
a
b
c
d
J3 J4 J5 J6 J7
1 2 2 1 1
(e)
a
b
c
d
J2 J3 J4
1 1 2
(c)
a
b
c
d
J1 J2 J3 J4 J5 J6 J7 J8
2 1 1 2 2 1 1 2
(f)
Figure 17: The six situations described in the proof of Theorem 8.5. In parts (a), (b) and
(c), there are too many guards in copy J2. In part (d), a1 is undefended. In part (e), a5 is
undefended. In part (f), the configuration of guards in J1, J2, J3, J4 is identical to that in
J5, J6, J7, J8.
weight w(f) <
⌈
3k+1
2
⌉
. This implies that w(f) ≤ 3k2 . Hence, from Lemma 8.3 we have
w(f) = 3k2 , each set of four consecutive copies has weight 6, and each copy has weight 1
or 2.
It is easy to check that there are only two possibilities. Either f has the repeating pattern
121212 . . . 12, or f has the repeating pattern 21122112 . . . 2112. Note that it is impossible
to combine these two patterns without there being a set of four consecutive copies with
weight not equal to 6. Then, since k ≥ 9, by Theorem 8.2 the pattern 121212 . . . 12
is impossible. Hence, f must have the repeating pattern 21122112 . . . 2112. Then, by
Theorem 8.5 there is weak Roman dominating function for Jk−4 with weight equal to
3k
2 − 6 <
⌈
3(k−4)+1
2
⌉
. This contradicts our initial assumption, completing the proof.
ORCID iDs
Michael Haythorpe https://orcid.org/0000-0001-8143-6583
Alex Newcombe https://orcid.org/0000-0002-4401-0951
References
[1] I. Agustin and D. Dafik, On the domination number of some families of special graphs, Prosid-
ing Seminar Matematika dan Pendidikan Matematik 1 (2014), https://jurnal.unej.
ac.id/index.php/psmp/article/view/921.
24 Ars Math. Contemp. 24 (2024) #P3.04
[2] S. Alanko, S. Crevals, A. Isopoussu, P. Östergård and V. Pettersson, Computing the domination
number of grid graphs, Electron. J. Comb. 18 (2011), research paper p141, 18 pp., doi:10.
37236/628, https://doi.org/10.37236/628.
[3] S. Arumugam and R. Kala, Domination parameters of hypercubes, J. Indian Math. Soc., New
Ser. 65 (1998), 31–38.
[4] A. Burcroff, Tightness of domination inequalities for direct product graphs, Discrete Math.
344 (2021), 10, doi:10.1016/j.disc.2021.112495, id/No 112495, https://doi.org/10.
1016/j.disc.2021.112495.
[5] R. Burdett and M. Haythorpe, An improved binary programming formulation for the secure
domination problem, Ann. Oper. Res. 295 (2020), 561–573, doi:10.1007/s10479-020-03810-6,
https://doi.org/10.1007/s10479-020-03810-6.
[6] R. Burdett, M. Haythorpe and A. Newcombe, Binary programming formulations for the upper
domination problem, Ann. Oper. Res. (2021), submitted.
[7] A. Burger, A. De Villiers and J. Van Vuuren, A binary programming approach towards achiev-
ing effective graph protection, in: Proc. 2013 ORSSA Annual Conf., ORRSA, pp. 19–30, 2013.
[8] T. Y. Chang and W. E. Clark, The domination numbers of the 5×n and 6×n grid graphs, J.
Graph Theory 17 (1993), 81–107, doi:10.1002/jgt.3190170110, https://doi.org/10.
1002/jgt.3190170110.
[9] S. Crevals and P. R. J. Östergard, On the domination number of 2-dimensional torus graphs,
Util. Math. 106 (2018), 289–300.
[10] N. Fan and J.-P. Watson, Solving the connected dominating set problem and power dominating
set problem by integer programming, in: Combinatorial optimization and applications. 6th
international conference, COCOA 2012, Springer, Berlin, pp. 371–383, 2012, doi:10.1007/
978-3-642-31770-5 33, https://doi.org/10.1007/978-3-642-31770-5_33.
[11] G. H. Fricke, S. M. Hedetniemi, S. T. Hedetniemi, A. A. McRae, C. K. Wallis, M. S. Jacobson,
H. W. Martin and W. D. Weakley, Combinatorial problems on chessboards: A brief survey, in:
Graph Theory, Combinatorics, Algorithms and Applications. Vol. 1. Proceedings of the seventh
quadrennial international conference on the theory and applications of graphs, Kalamazoo,
MI, USA, June 1-5, 1992, Wiley, New York, NY, pp. 507–528, 1995.
[12] X. Fu, X. Xu, Y. Yang and X. Feng, On the domination number of Knödel graph W3,n, Int. J.
Pure Appl. Math. 50 (2009), 553–558.
[13] X. Fu, Y. Yang and B. Jiang, On the domination number of generalized petersen graphs
P (n, 2), Discrete Math. 309 (2009), 2445–2451, doi:10.1016/j.disc.2008.05.026, https:
//doi.org/10.1016/j.disc.2008.05.026.
[14] D. Gonçalves, A. Pinlou, M. Rao and S. Thomassé, The domination number of grids, SIAM
J. Discrete Math. 25 (2011), 1443–1453, doi:10.1137/11082574, https://doi.org/10.
1137/11082574.
[15] S. Gravier, Total domination number of grid graphs, Discrete Appl. Math. 121
(2002), 119–128, doi:10.1016/S0166-218X(01)00297-9, https://doi.org/10.1016/
S0166-218X(01)00297-9.
[16] E. Hare, Algorithms for Grids and Grid-Like Graphs, Ph.D. thesis, Clemson University, 1989.
[17] M. Haythorpe and A. Newcombe, The secure domination number of Cartesian products of
small graphs with paths and cycles, Discrete Appl. Math. 309 (2022), 32–45, doi:10.1016/j.
dam.2021.11.008, https://doi.org/10.1016/j.dam.2021.11.008.
[18] J. T. Hedetniemi and S. T. Hedetniemi, Domination in chessboards, in: Structures of Domi-
nation in Graphs, Springer, Cham, pp. 341–386, 2021, doi:10.1007/978-3-030-58892-2 12,
https://doi.org/10.1007/978-3-030-58892-2_12.
R. Burdett et al.: Variants of the domination number for flower snarks 25
[19] R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Am.
Math. Mon. 82 (1975), 221–239, doi:10.2307/2319844, https://doi.org/10.2307/
2319844.
[20] M. S. Jacobson and L. F. Kinch, On the domination number of products of graphs. I, Ars Comb.
18 (1984), 33–44.
[21] A. Klobučar, Total domination numbers of Cartesian products, Math. Commun. 9 (2004), 35–
44.
[22] J. Kratica, D. Matić and V. Filipović, Weakly convex and convex domination numbers for
generalized Petersen and flower snark graphs, Rev. Unión Mat. Argent. 61 (2020), 441–455,
doi:10.33044/revuma.v61n2a16, https://doi.org/10.33044/revuma.v61n2a16.
[23] Y. Lai, C. Lin and H. Ho, Weak roman domination on graphs, in: Proceedings of the 28th
workshop on combinatorial mathematics and computation theory, Penghu University of Science
and Technology, Penghu, Taiwan, May 27–28, 2011, 2011.
[24] J. Liu and X. Zhang, The exact domination number of generalized Petersen graphs P (n, k)
with n = 2k and n = 2k + 2∗, Comput. Appl. Math. 33 (2014), 497–506, doi:10.1007/
s40314-013-0077-8, https://doi.org/10.1007/s40314-013-0077-8.
[25] Z. Maksimovic, J. Kratica, A. Savić and M. Bogdanović, Some static roman domination num-
bers for flower snarks, in: XIII Balkan Conference on Operational Research Proceedings, 2018.
[26] D. Mojdeh, M. Habibi and L. Badakhshian, Total and connected domination in chemical
graphs, Ital. J. Pure Appl. Math. 39 (2018), 393–401.
[27] D. A. Mojdeh, R. S. Musawi, E. Nazari Kiashi and N. Jafari Rad, Total domination in cubic
Knödel graphs, Commun. Comb. Optim. 6 (2021), 221–230, doi:10.22049/cco.2020.26793.
1143, https://doi.org/10.22049/cco.2020.26793.1143.
[28] P. Pavlič and J. Žerovnik, A note on the domination number of the Cartesian products of paths
and cycles, Kragujevac J. Math. 37 (2013), 275–285.
[29] S. Pouyandeh, M. Golriz, M. Sorouhesh and M. Khademi, On domination number of
Latin square graphs of finite cyclic groups, Discrete Math. Algorithms Appl. 13 (2021),
8, doi:10.1142/s1793830920500901, id/No 2050090, https://doi.org/10.1142/
s1793830920500901.
[30] P. R. L. Pushpam and M. Kamalam, Weak Roman domination in chess graphs, Malaya J.
Mat. 9 (2021), 486–493, doi:10.26637/MJM0901/0082, https://doi.org/10.26637/
MJM0901/0082.
[31] P. R. L. Pushpam and C. Suseendran, Secure domination in middle graphs, Bull. Int. Math.
Virtual Inst. 9 (2019), 25–38.
[32] J. Quadras, A. Sajiya Merlin Mahizl, I. Rajasingh and S. R. Rajan, Domination in cer-
tain chemical graphs, J. Math. Chem. 53 (2015), 207–219, doi:10.1007/s10910-014-0422-1,
https://doi.org/10.1007/s10910-014-0422-1.
[33] E. Sampathkumar and H. B. Walikar, The connected domination number of a graph, J. Math.
Phys. Sci. 13 (1979), 607–613.
[34] L. Shan, H. Li and Z. Zhang, Domination number and minimum dominating sets in pseud-
ofractal scale-free web and Sierpiński graph, Theor. Comput. Sci. 677 (2017), 12–30, doi:
10.1016/j.tcs.2017.03.009, https://doi.org/10.1016/j.tcs.2017.03.009.
[35] A. Shobana and P. Senniappan, Connected domination number in circulant graphs, J.
Math. Anal. 9 (2015), 2485–2488, doi:10.12988/ijma.2015.59228, https://doi.org/
10.12988/ijma.2015.59228.
26 Ars Math. Contemp. 24 (2024) #P3.04
[36] A. Spalding, Min-Plus Algebra and Graph Domination, Ph.D. thesis, University of Colorado,
1998.
[37] M. Valveny and J. A. Rodrı́guez-Velázquez, Protection of graphs with emphasis on Cartesian
product graphs, Filomat 33 (2019), 319–333, doi:10.2298/FIL1901319V, https://doi.
org/10.2298/FIL1901319V.
[38] A. Vijayan and M. F. N. Mabel, Connected dominating sets and connected domination
polynomials of square of centipedes, Journal of Information and Optimization Sciences 37
(2016), 155–165, doi:10.1080/02522667.2015.1103031, https://doi.org/10.1080/
02522667.2015.1103031.
[39] C. Wallis, Domination parameters of line graphs of designs and variations of chessboard
graphs, Ph.D. thesis, Clemson University, 1996.
[40] A. M. Yaglom and I. M. Yaglom, Challenging mathematical problems with elementary solu-
tions. Vol. I, 1967.
[41] H. Yan, L. Kang and G. Xu, The exact domination number of the generalized Petersen
graphs, Discrete Math. 309 (2009), 2596–2607, doi:10.1016/j.disc.2008.04.026, https:
//doi.org/10.1016/j.disc.2008.04.026.