ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.03
https://doi.org/10.26493/1855-3974.2637.f61
(Also available at http://amc-journal.eu)
Domination type parameters of Pell graphs*
Arda Buğra Özer
Middle East Technical University, Northern Cyprus Campus, Kalkanlı, Güzelyurt,
Mersin 10, Turkey
Elif Saygı
Department of Mathematics and Science Education, Hacettepe University, Ankara, Turkey
Zülfükar Saygı †
Department of Mathematics, TOBB University of Economics and Technology, Ankara,
Turkey
Received 20 May 2021, accepted 7 March 2022, published online 12 September 2022
Abstract
Pell graphs are defined on certain ternary strings as special subgraphs of Fibonacci
cubes of odd index. In this work the domination number, total domination number, 2-
packing number, connected domination number, paired domination number, and signed
domination number of Pell graphs are studied. Using integer linear programming, exact
values and some estimates for these numbers of small Pell graphs are obtained. Further-
more, some theoretical bounds are obtained for the domination numbers and total domina-
tion numbers of Pell graphs.
Keywords: Pell graphs, Fibonacci cube, domination number, integer linear programming.
Math. Subj. Class. (2020): 05C69, 68R10
1 Introduction
One of the basic models for interconnection networks is the n-dimensional hypercube
graph Qn. It has 2n vertices, represented by all binary strings of length n, and two ver-
tices in Qn are adjacent if they differ in exactly one coordinate. For convenience, we set
*This work is partially supported by TÜBİTAK under Grant No. 120F125. The authors are grateful to the
anonymous reviewers for their valuable comments and careful reading.
†Corresponding author.
E-mail addresses: abozer@metu.edu.tr (Arda Buğra Özer), esaygi@hacettepe.edu.tr (Elif Saygı),
zsaygi@etu.edu.tr (Zülfükar Saygı)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P1.03
Q0 = K1. The n dimensional Fibonacci cube Γn is defined as the subgraph of Qn induced
by the vertices whose string representations are Fibonacci strings. They were introduced
by Hsu [10] as an alternative model for interconnection networks and extensively studied
in the literature [13]. There are numerous subgraphs and variants of Fibonacci cubes in the
literature, such as Lucas cubes [15], generalized Fibonacci cubes [11], k-Fibonacci cubes
[5] and Pell graphs [14].
Let G = (V,E) be a graph with vertex set V = V (G) and edge set E = E(G). A set
D ⊆ V is called a dominating set of G if every vertex in V \D is adjacent to some vertex
in D. Then the domination number γ(G) of G is defined as the minimum cardinality of a
dominating set of G. Similarly, a set D ⊆ V is called a total dominating set of a graph G
without isolated vertices, if every vertex in V is adjacent to some vertex in D and the total
domination number γt(G) ofG is defined as the minimum cardinality of a total dominating
set of G.
The domination type parameters of Fibonacci and Lucas cubes are first considered in
[3, 17]. Using integer linear programming, domination and total domination numbers of
these cubes and some additional domination type parameters of these cubes [2, 12] and hy-
percubes [2] are considered in the literature. Furthermore, upper bounds and lower bounds
on domination and total domination numbers of Fibonacci and Lucas cubes are obtained in
[2, 3, 17, 18, 19, 20]. The domination and total domination number of k-Fibonacci cubes
are considered in [6]. In this work, we studied some domination type parameters of Pell
graphs.
2 Preliminaries
Let fn denote the Fibonacci numbers defined as f0 = 0, f1 = 1 and fn = fn−1 + fn−2
for n ≥ 2. Similarly, let pn denote the Pell numbers defined as p0 = 1, p1 = 2 and
pn = 2pn−1 + pn−2 for n ≥ 2. Here we remark that the generating function of pn (see,
for example [9]) is ∑
n≥0
pnx
n =
1
1− 2x− x2
. (2.1)
Binary strings of length n not containing two consecutive 1s constitute the set of Fi-
bonacci strings Fn of length n, that is, the binary strings b1b2 . . . bn such that bi · bi+1 = 0
for all i = 1, 2, . . . , n− 1.
Ternary strings over the alphabet {0, 1, 2} where there are no maximal blocks of 2s
of odd length constitute the set of Pell strings, Pn. Then the n dimensional Pell graph,
Πn, is defined as the simple graph where the vertices are represented by the Pell strings
of length n, and two vertices are adjacent whenever one of them can be obtained from the
other by replacing a 0 with a 1 (or vice versa), or by replacing a factor 11 with 22 (or vice
versa) [14]. The vertices of Πn can be partitioned into vertices that start with 0, vertices
that start with 1 and vertices that start with 22. The subgraphs induced by these vertices
are isomorphic to Πn−1, Πn−1, and Πn−2, respectively. This gives the following canonical
decomposition of Pell graphs for n ≥ 2
Πn = 0Πn−1 + 1Πn−1 + 22Πn−2, (2.2)
where Π0 = K1 and Π1 = K2. Here remark that we have also to add the edges of perfect
matchings between 0Πn−1 and 1Πn−1; and also between 22Πn−2 and 11Πn−1 (an induced
subgraph of 1Πn−1).
A. Buğra Özer et al.: Domination type parameters of Pell graphs 3
Every Pell string decomposes uniquely into the product of the factors 0, 1 and 22. Let
ψ : Pn → F2n where ψ(0) = 10, ψ(1) = 00 and ψ(22) = 0100. Hence, we know that
ψ maps any Pell string of length n to a unique Fibonacci string of length 2n with no 0101
factors and without a final 1, which are called Pell binary strings. For a graphG, we denote
a subgraphH ofG byH ⊆ G. Then using this notation and the ψ mapping it is shown that
Theorem 2.1 ([14, Theorem 7]). For n ≥ 1, we have the inclusion Πn ⊆ Γ2n−1.
Let Γ∗2n be the Hamming graph generated by the set of all Pell binary strings of length
2n then we have the following result showing that Πn is isomorphic to an induced subgraph
of Γ2n−10.
Theorem 2.2 ([14, Theorem 8]). The graphs Πn and Γ∗2n are isomorphic.
Let N(v) denote the open neighborhood of v ∈ V , that is, the set of vertices adjacent
to v, and N [v] = N(v) ∪ {v}. Using Theorem 2.1, we have the following Lemma.
Lemma 2.3. Let v ∈ Πn ⊆ Γ2n−10. For any u ∈ N(v) ⊆ Γ2n−10, the binary string
representation of u can not have two non-overlapping 0101 factors as a substring.
Proof. Assume that there is a vertex u ∈ N(v) of the form α10101α20101α30 ∈ F2n−10.
Then we know that the distance between u and v in Γ2n−1 is 1. Hence, v should have a
0101 factor, which is a contradiction.
Let α0(0101)0β ∈ F2n for some Fibonacci strings α and β which do not have a 0101
factor. Let us define the maps ϕ1, ϕ2 and ϕ from F2n into F2n by setting
ϕ1(α0(0101)0β) = α0(0001)0β,
ϕ2(α0(0101)0β) = α0(0100)0β,
ϕ(α0(0101)0β) = α0(0000)0β.
3 Main results
We first interrelate the domination and total domination numbers of Fibonacci cubes and
Pell graphs using Theorem 2.1 and Lemma 2.3.
Proposition 3.1. For any positive integer n, we have
(i) γ(Πn) ≤ γ(Γ2n−1)
(ii) γt(Πn) ≤ γt(Γ2n−1)
Proof. (i) Let D be a minimal dominating set of Γ2n−1 and set
D′ = {α | α is a Pell binary string from D0}∪
∪ {ϕ(β0) | β0 ∈ D0 has one 0101 factor}.
Note that |D′| ≤ |D|. Let u be a vertex of Πn. Then the vertex ψ(u) is dominated in
Γ2n−10 by some d0 ∈ D0. If d0 is a Pell binary string then d0 belongs to D′. If d0 is not
a Pell binary string then we know that it has only one 0101 factor and ψ(u) must be of the
form ϕ1(d0) or ϕ2(d0), which are also dominated by a Pell binary string ϕ(d0). Then we
obverse that D′ is a dominating set of Πn. Hence, we have γ(Πn) ≤ γ(Γ2n−1).
4 Ars Math. Contemp. 23 (2023) #P1.03
(ii) Using the same argument in the previous part, assume that D is a minimal total
dominating set of Γ2n−1. Then we merely need to show that D′ is a total dominating set.
Since D is a total dominating set in Γ2n−1, we know that every vertex v ∈ V (Πn) ⊆
V (Γ2n−10) must be adjacent to some vertex w ∈ D0. If w ∈ D′, there is nothing to show.
Otherwise, w must have one 0101 factor. Since Pell binary string representations of the
vertices in Πn do not have a 0101 factor, v ∈ V (Πn) must be of the form ϕ1(w) or ϕ2(w).
Hence, v is also adjacent to ϕ(w) ∈ D′.
Using the canonical decomposition (2.2) of Πn, we obtain the following results.
Proposition 3.2. For any integer n ≥ 3, we have
(i) γ(Πn) ≤ 2γ(Πn−1) + γ(Πn−2)
(ii) γt(Πn) ≤ 2γ(Πn−1) + γt(Πn−2)
(iii) γ(Πn) ≤ γt(Πn) ≤ 5γ(Πn−2) + 2γ(Πn−3)
Proof. (i) This follows directly from the canonical decomposition (2.2) of Pell graphs.
(ii) Let D1 be a dominating set for Πn−1 and D2 be a total dominating set for Πn−2.
From (2.2) we know that there is a perfect matching between 0Πn−1 and 1Πn−1. Using
this perfect matching, we conclude that the set 0D1 ∪ 1D1 ∪ 22D2 is a total dominating set
for Πn, which gives the desired result.
(iii) This follows from using the canonical decomposition (2.2) of Pell graphs recur-
sively and the perfect matchings between the induced subgraphs, namely 5 copies of Πn−2
and 2 copies of Πn−3.
Considering the vertices of high degrees, lower bounds on γ(Γn) and γ(Λn) are ob-
tained in [17, Theorem 3.2] and [3, Theorem 3.5.], respectively. Using the same argument,
we obtain the lower bound for γ(Πn) in Proposition 3.4. Before we introduce this lower
bound, we have the following remark on the degree distribution of the vertices of Πn.
Remark 3.3. We know that Πn is an induced subgraph of Γ2n−10, which means that the
degrees of the vertices of Πn is at most 2n − 1. It is shown in [14, Proposition 27] that
1n is the unique vertex having degree 2n − 1 for n ≥ 2. Using the recursive relation in
[14, Theorem 29], which gives the number of all vertices of Πn having fixed degree, it is
easy to show that for n ≥ 3, there are only 2 vertices having degree 2n− 2 (namely, 01n−1
and 1n−10), and for n ≥ 4 there are exactly n+ 1 vertices having degree 2n− 3. The rest
of the vertices of Πn have degree at most 2n− 4 for n ≥ 4.
Proposition 3.4. For any n ≥ 7, we have γt(Πn) ≥ γ(Πn) ≥
⌈
pn − n− 8
2n− 3
⌉
.
Proof. Let D be a minimum dominating set of Πn and define the over domination of Πn
with respect to D as
OD(Πn) =
(∑
v∈D
(
deg(v) + 1
))
− |V (Πn)| .
A. Buğra Özer et al.: Domination type parameters of Pell graphs 5
Let S = {v ∈ V (Πn) | deg(v) ≥ 2n− 3}. Using Remark 3.3, we have
0 ≤ OD(Πn) = 2n+ 2(2n− 1) + (n+ 1)(2n− 2)− pn +
∑
v∈D\S
(
deg(v) + 1
)
≤ 2n2 + 6n− 4− pn + (|D| − |S|)(2n− 3)
= n+ 8− pn + |D|(2n− 3)
which gives the desired result.
3.1 Integer linear programming for domination numbers
Suppose each vertex v ∈ V (Πn) is associated with a binary variable xv . The problems of
determining γ(Πn) and γt(Πn) can be expressed as problems of minimizing the objective
function ∑
v∈V (Πn)
xv (3.1)
subject to the following constraints for every v ∈ V (Λn):∑
a∈N [v]
xa ≥ 1 (for domination number),
∑
a∈N(v)
xa ≥ 1 (for total domination number).
The value of the objective function (3.1) gives γ(Πn) and γt(Πn), respectively. Note that
this problem has pn binary variables and pn constraints.
We implemented the integer linear programming problem (3.1) on Intel Core i7-10875H
CPU @ 2.30GHz with 32GB RAM running the Ubuntu 20.04 LTS Linux operating system
and using Gurobi Optimizer [8]. We obtain the exact values of γ(Πn) for n ≤ 6 and γt(Πn)
for n ≤ 7. Furthermore, we obtain the estimates 60 ≤ γ(Π7) ≤ 64 (takes approximately
1 hour) and 137 ≤ γ(Π7) ≤ 162 (takes approximately 1 hour) . We collect the values of
γ(Πn) and γt(Πn) that we obtained from (3.1) in Table 1. In Tables 2 and 3 we present
examples of a minimal dominating and total dominating sets that were obtained during the
computation of these values. We also present an example of a dominating set of Π7 having
cardinality 64 in Appendix (see, Table 11).
Table 1: Domination and total domination numbers for small Pell graphs.
n 1 2 3 4 5 6 7 8
|V (Πn)| 2 5 12 29 70 169 408 985
γ(Πn) 1 2 4 7 14 30 60−64
γt(Πn) 2 2 4 9 16 34 72 137−162
Using the computation results presented in Table 1, Proposition 3.2 and a simple induc-
tion argument we obtain the following results.
Theorem 3.5. For n ≥ 6, we have γ(Πn) ≤ 22pn−4 − 40pn−5 ; and for n ≥ 9, we have
γt(Πn) ≤ 22pn−4 − 40pn−5 .
6 Ars Math. Contemp. 23 (2023) #P1.03
Proof. From Proposition 3.2 and Table 1, we know that
γ(Πn) ≤ 2γ(Πn−1) + γ(Πn−2) (3.2)
and γ(Π6) = 30, γ(Π7) ≤ 64. We set s6 = 30, s7 = 64 and sn = 2sn−1 + sn−2 for
n ≥ 8. Using (3.2), one can easily see that γ(Πn) ≤ sn for n ≥ 6. Let S =
∑
n≥0 sn+6x
n
be the generating function of the sequence sn+6. Therefore, S satisfies
S − 30− 64x = 2x(S − 30) + x2S
which gives
S =
30 + 4x
1− 2x− x2
.
Then using (2.1), we obtain sn+7 = 30pn+1 + 4pn for n ≥ 0 and s6 = 30p0. This is
equivalent to sn = 22pn−4 − 40pn−5 for all n ≥ 6. Using a similar argument, we obtain
the desired result for the total domination number.
Remark 3.6. For any graph G of minimum degree δ, a general upper bound due to Arnau-
tov [1] and Payan [16] is
γ(G) ≤ |V (G)|
δ + 1
δ+1∑
j=1
1
j
. (3.3)
We know that δ(Πn) = ⌈n2 ⌉ (cf. [14, Proposition 27]). Computing the upper bound in
Theorem 3.5 and the right-hand side of the bound (3.3) for γ(Πn), we observe that our
bound from Theorem 3.5 is better than the bound from (3.3) for n ≤ 44.
Table 2: Example of a minimal dominating set for Π6.
000000, 000221, 001022, 001101, 001110, 001122,
010011, 010110, 012200, 022000, 022111, 022220,
100011, 100220, 101100, 102211, 110101, 110122,
111001, 111010, 111221, 112211, 112222, 122022,
122100, 220000, 220022, 220220, 221111, 222200.
Table 3: Example of a minimal total dominating set for Π7.
0000000, 0001022, 0001122, 0001220, 0001221, 0002211, 0010000, 0010011,
0010111, 0011100, 0012211, 0022011, 0022100, 0100101, 0100111, 0101010,
0101101, 0110220, 0111220, 0122011, 0122111, 0122220, 0220111, 0220122,
0221000, 0221001, 0221122, 0222200, 0222210, 1000110, 1000111, 1001001,
1002200, 1010111, 1011001, 1011010, 1011110, 1022111, 1022122, 1022221,
1100022, 1100220, 1101010, 1102200, 1102210, 1102222, 1110001, 1110010,
1110022, 1110100, 1110220, 1111022, 1112201, 1112222, 1122000, 1122001,
1220010, 1220100, 1221111, 1221221, 2200000, 2200111, 2201000, 2201111,
2201221, 2210001, 2210111, 2211022, 2211110, 2212201, 2222110, 2222111.
A. Buğra Özer et al.: Domination type parameters of Pell graphs 7
3.2 Additional domination type parameters of small Pell graphs
By using the integer linear programming approach several additional parameters of small
Fibonacci cubes, Lucas cubes and k-Fibonacci cubes are obtained in [2, 6, 12, 20]. In
this section we use a similar approach to obtain domination type parameters of small Pell
graphs. For completeness of the paper, we first give the definition of these parameters and
corresponding linear optimization problems similar to (3.1).
A set X ⊆ V is a 2-packing if the distance d(u, v) ≥ 3 for any u, v ∈ X , u ̸= v. The
maximum size of a 2-packing of G is the 2-packing number of G denoted ρ(G). It can be
determined using the following optimization problem:
ρ(G) =max
∑
v∈V
xv
subject to
∑
u∈N [v]
xu ≤ 1, for all v ∈ V.
The independent domination number i(G) is the minimum size of a dominating set that
induces no edges (or, equivalently, the size of the smallest maximal independent set), which
can be determined using the following optimization problem:
i(G) =min
∑
v∈V
xv
subject to
∑
u∈N [v]
xu ≥ 1, for all v ∈ V
(|V | − 1)xv +
∑
u∈N(v)
xu ≤ |V | − 1, for all v ∈ V.
A set X ⊆ V is a k-tuple dominating set of G if for every vertex v ∈ V we have
|N [v]∩X| ≥ k, that is, v ∈ X and has at least k−1 neighbors in S or v ∈ V \X has at least
k neighbors inX . The k-tuple domination number γ×k(G) is the minimum cardinality of a
k-tuple dominating set of G. Clearly, γ(G) = γ×1(G) ≤ γ×k(G), while γt(G) ≤ γ×2(G)
and γ×k(G) can be determined using the following optimization problem:
γ×k(G) =min
∑
v∈V
xv
subject to
∑
u∈N [v]
xu ≥ k, for all v ∈ V.
Specifically, a k-tuple dominating set where k = 2 is called a double dominating set and in
this work we determine double domination number γ×2(Πn) of small Pell graphs.
A function f : V → {−1, 1} is called a signed dominating function if
∑
u∈N [v] f(u) ≥
1 holds for every v ∈ V [4]. The signed domination number γs(G) of G is the minimum
of
∑
v∈V f(v) taken over all signed dominating functions f of G and it can be determined
using the following optimization problem [2]:
γs(G) =min
∑
v∈V
(2xv − 1)
subject to
∑
u∈N [v]
(2xu − 1) ≥ 1, for all v ∈ V.
8 Ars Math. Contemp. 23 (2023) #P1.03
Here we note that binary variables xv associated with every vertex v ∈ V indicates whether
v is assigned weight 1 (xv = 1) or −1 (xv = 0).
The connected domination number γc(G) is the order of a smallest dominating set that
induces a connected graph. We used the Miller-Tucker-Zemlin constraints to find a minimal
connected domination set for Pell graphs [7].
The paired domination number γp(G) is the order of a smallest dominating set S ⊆ V
s.t. the graph induced by S contains a perfect matching. We associate to each edge e =
uv ∈ E a binary variable xe = xuv indicating whether e is present in the graph induced by
a paired dominating set. Then the following optimization problem determines γp(G) [2]:
γp(G) = 2 ·min
∑
e∈E
xe
subject to
∑
u∈N(v)
xuv ≤ 1, for all v ∈ V
∑
u∈N(v)
∑
w∈N(u)
xuw ≥ 1, for all v ∈ V.
Using the integer linear programming approaches described in this section, we obtain
the values and estimates of ρ(Πn), i(Πn), γ×2(Πn), γs(Πn), γc(Πn), γp(Πn) for some
small values of n and collect these results in Table 4. Furthermore, in Tables 5, 6, 7, 9
and 10 in Appendix, we present example of a set of vertices giving ρ(Πn) and γp(Πn) for
n = 7, γc(Πn) for n = 5, and i(Πn) and γ×2(Πn) for n = 6 that were obtained during the
computation of these values. In Table 8, we also present the set of vertices v ∈ V (Π6) for
which f(v) = −1, where f is a signed dominating function giving γs(Π6) = 45.
Table 4: Values of additional domination type parameters for small Pell graphs.
n 1 2 3 4 5 6 7
|V (Πn)| 2 5 12 29 70 169 408
ρ(Πn) 1 2 3 6 11 22 46
i(Πn) 1 2 4 7 15 31 60−69
γ×2(Πn) 2 4 7 13 27 56 113−121
γs(Πn) 2 3 4 11 20 45 88−102
γc(Πn) 1 2 4 9 18 35−38 66−82
γp(Πn) 2 2 4 10 16 34 72
ORCID iDs
Arda Buğra Özer https://orcid.org/0000-0002-6505-7038
Elif Saygı https://orcid.org/0000-0001-8811-4747
Zülfükar Saygı https://orcid.org/0000-0002-7575-3272
References
[1] V. I. Arnautov, Estimation of the exterior stability number of a graph by means of the minimal
degree of the vertices, Prikl. Mat. i Programmirovanie (1974), 3–8, 126.
A. Buğra Özer et al.: Domination type parameters of Pell graphs 9
[2] J. Azarija, S. Klavžar, Y. Rho and S. Sim, On domination-type invariants of Fibonacci cubes
and hypercubes, Ars Math. Contemp. 14 (2018), 387–395, doi:10.26493/1855-3974.1172.bae,
https://doi.org/10.26493/1855-3974.1172.bae.
[3] A. Castro, S. Klavžar, M. Mollard and Y. Rho, On the domination number and
the 2-packing number of Fibonacci cubes and Lucas cubes, Comput. Math. Appl. 61
(2011), 2655–2660, doi:10.1016/j.camwa.2011.03.012, https://doi.org/10.1016/
j.camwa.2011.03.012.
[4] J. Dunbar, S. Hedetniemi, M. A. Henning and P. J. Slater, Signed domination in graphs, in:
Graph theory, Combinatorics, and Algorithms, Vol. 1, 2, Wiley, New York, Wiley-Intersci.
Publ., pp. 311–321, 1995.
[5] Ö. Eğecioğlu, E. Saygı and Z. Saygı, k-Fibonacci cubes: a family of subgraphs of Fibonacci
cubes, Int. J. Found. Comput. Sci. 31 (2020), 639–661, doi:10.1142/s0129054120500318,
https://doi.org/10.1142/s0129054120500318.
[6] Ö. Eğecioğlu, E. Saygı and Z. Saygı, On the chromatic polynomial and the domination num-
ber of k-Fibonacci cubes, Turkish J. Math. 44 (2020), 1813–1823, doi:10.3906/mat-2004-20,
https://doi.org/10.3906/mat-2004-20.
[7] 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, Springer, Heidelberg, volume 7402 of Lecture Notes in Comput. Sci.,
pp. 371–383, 2012, doi:10.1007/978-3-642-31770-5 33, https://doi.org/10.1007/
978-3-642-31770-5_33.
[8] Gurobi Optimization, Gurobi optimizer reference manual, 2021, http://www.gurobi.
com.
[9] A. F. Horadam, Pell identities, Fibonacci Quart. 9 (1971), 245–252, 263, https://www.
fq.math.ca/9-3.html.
[10] W.-J. Hsu, Fibonacci cubes–a new interconnection technology, IEEE Trans. Parallel Dis-
trib. Syst. 4 (1993), 3–12, doi:10.1109/71.205649, https://doi.org/10.1109/71.
205649.
[11] A. Ilić, S. Klavžar and Y. Rho, Generalized Fibonacci cubes, Discrete Math. 312 (2012),
2–11, doi:10.1016/j.disc.2011.02.015, https://doi.org/10.1016/j.disc.2011.
02.015.
[12] A. Ilić and M. Milošević, The parameters of Fibonacci and Lucas cubes, Ars Math. Contemp.
12 (2017), 25–29, doi:10.26493/1855-3974.915.f48, https://doi.org/10.26493/
1855-3974.915.f48.
[13] S. Klavžar, Structure of Fibonacci cubes: a survey, J. Comb. Optim. 25 (2013), 505–522, doi:
10.1007/s10878-011-9433-z, https://doi.org/10.1007/s10878-011-9433-z.
[14] E. Munarini, Pell graphs, Discrete Math. 342 (2019), 2415–2428, doi:10.1016/j.disc.2019.05.
008, https://doi.org/10.1016/j.disc.2019.05.008.
[15] E. Munarini, C. Perelli Cippo and N. Zagaglia Salvi, On the Lucas cubes, Fibonacci Quart. 39
(2001), 12–21, https://www.fq.math.ca/39-1.html.
[16] C. Payan, Sur le nombre d’absorption d’un graphe simple, Cahiers Centre Études Rech. Opér.
17 (1975), 307–317.
[17] D. A. Pike and Y. Zou, The domination number of Fibonacci cubes, J. Comb. Math. Comb.
Comput. 80 (2012), 433–444.
[18] E. Saygı, Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes,
SDU J. Nat. Appl. Sci. 21 (2017), 782–785, https://dergipark.org.tr/tr/pub/
sdufenbed/issue/34610/382218.
10 Ars Math. Contemp. 23 (2023) #P1.03
[19] E. Saygı, On the domination number and the total domination number of Fibonacci cubes, Ars
Math. Contemp. 16 (2019), 245–255, doi:10.26493/1855-3974.1591.92e, https://doi.
org/10.26493/1855-3974.1591.92e.
[20] Z. Saygı, Results on the domination number and the total domination number of Lucas cubes,
Ars Math. Contemp. 19 (2020), 25–35, doi:10.26493/1855-3974.2028.cb4, https://doi.
org/10.26493/1855-3974.2028.cb4.
A. Buğra Özer et al.: Domination type parameters of Pell graphs 11
Appendix
Table 5: Example of a 2-packing set for Π7.
0000110, 0001001, 0010000, 0010122, 0011221, 0012201, 0022022, 0022110,
0100022, 0100221, 0101100, 0102222, 0110101, 0111011, 0122000, 0220010,
0221122, 0221220, 0222200, 1000101, 1001022, 1002210, 1010011, 1010220,
1011100, 1012222, 1022001, 1100010, 1101111, 1122122, 1122220, 1220022,
1220100, 1220221, 1221001, 1222211, 2200122, 2200220, 2201000, 2202201,
2210001, 2211022, 2211221, 2212210, 2222010, 2222101.
Table 6: Example of a minimal independent dominating set for Π6.
000000, 000221, 001011, 001122, 001220, 002200, 010011, 010110,
010122, 011101, 012211, 022000, 022022, 022220, 100022, 100101,
100110, 101000, 102211, 111001, 111010, 111100, 111221, 112222,
122111, 220000, 220111, 220220, 221022, 222201, 222210.
Table 7: Example of a minimal double dominating set for Π6.
000000, 000022, 000111, 000220, 001022, 001100, 001101, 001110,
002211, 010000, 010010, 010101, 010220, 011011, 011101, 011122,
011221, 012210, 012211, 022000, 022011, 022022, 022110, 022220,
100001, 100110, 100111, 101001, 101010, 101221, 102200, 102211,
102222, 110022, 110100, 110122, 111010, 111022, 111122, 111220,
111221, 112200, 122000, 122101, 122111, 220001, 220011, 220100,
220220, 220221, 221001, 221010, 221110, 221122, 222201, 222211.
12 Ars Math. Contemp. 23 (2023) #P1.03
Table 8: The set of vertices v ∈ V (Π6) for which f(v) = −1, where f is a signed
dominating function giving γs(Π6) = 45.
000001, 000010, 000101, 000110, 000122, 001010, 001022, 001101,
001110, 001221, 002222, 010001, 010100, 010122, 010220, 011001,
011011, 011100, 011111, 011221, 012200, 012211, 022010, 022022,
022100, 022122, 022220, 100000, 100011, 100111, 100221, 101000,
101022, 101101, 101110, 102201, 102210, 102222, 110000, 110011,
110100, 110111, 110220, 111011, 111110, 111111, 122001, 122010,
122101, 122220, 220010, 220022, 220101, 220122, 220220, 221001,
221010, 221101, 221221, 222200, 222210, 222222.
Table 9: Example of a minimal connected dominating set for Π5.
00011, 00101, 00111, 00221, 01000, 01111,
01122, 02201, 02211, 10011, 11000, 11100,
11110, 11111, 11122, 11220, 22011, 22111.
Table 10: Example of a minimal paired dominating set for Π7.
0000000, 0000100, 0000220, 0001022, 0001122, 0001220, 0010111, 0011001,
0011010, 0011100, 0011111, 0012200, 0022001, 0022220, 0100011, 0100111,
0101101, 0102201, 0110022, 0111110, 0112222, 0122011, 0122111, 0220000,
0220111, 0221000, 0221110, 0221111, 1000011, 1000111, 1001101, 1002210,
1002211, 1010010, 1011010, 1011101, 1022022, 1022122, 1022220, 1101000,
1101010, 1101221, 1102210, 1110001, 1110010, 1110022, 1110100, 1110101,
1110122, 1110220, 1110221, 1111221, 1112222, 1122000, 1122100, 1220220,
1221011, 1221022, 1222200, 1222201, 2200110, 2200111, 2201000, 2201022,
2201122, 2202201, 2210001, 2211110, 2211220, 2212201, 2222011, 2222111.
Table 11: Example of a dominating set having 64 vertices for Π7.
0000010, 0001001, 0002211, 0010022, 0010101, 0010221, 0011100, 0011110,
0022010, 0022122, 0100000, 0100111, 0101022, 0101220, 0102200, 0110000,
0111100, 0111110, 0112222, 0122001, 0122221, 0220000, 0220122, 0220220,
0221011, 0222201, 1000001, 1000100, 1000122, 1000220, 1001122, 1001221,
1002210, 1011000, 1011011, 1012201, 1022101, 1022220, 1101010, 1101101,
1110010, 1110011, 1110110, 1110111, 1112222, 1122000, 1122022, 1220101,
1221000, 1221022, 1221221, 1222210, 2200022, 2200100, 2200221, 2201010,
2202211, 2210001, 2211001, 2211122, 2211220, 2212200, 2222110, 2222111.