@
Appl. Gen. Topol. 21, no. 2 (2020), 305-325

doi:10.4995/agt.2020.13553

c© AGT, UPV, 2020

The higher topological complexity in

digital images

Melih İs and İsmet Karaca

Department of Mathematics, Ege University, İzmir, Turkey (melih.is@ege.edu.tr, ismet.karaca@ege.edu.tr)

Communicated by S. Romaguera

Abstract

Y. Rudyak develops the concept of the topological complexity TC(X)
defined by M. Farber. We study this notion in digital images by using
the fundamental properties of the digital homotopy. These properties
can also be useful for the future works in some applications of alge-
braic topology besides topological robotics. Moreover, we show that
the cohomological lower bounds for the digital topological complexity
TC(X, κ) do not hold.

2010 MSC: 46M20; 68U05; 68U10; 68T40; 62H35.

Keywords: topological complexity; digital topology; homotopy theory; di-
gital topological complexity; image analysis.

1. Introduction

One of the most popular topics in the field of applications of algebraic
topology in recent years arises from the interpretation of algebraic topological
elements in the area of robotics. After M. Farber put it in the literature for
the first time [17], this subject has been studied by many researchers [13], [18],
[19], [20], [23] and [28] since that time. This is very important because these
studies can shed light on further engineering and navigation problems. For this
purpose, it is necessary to understand how tools of algebraic topology take a
place in the problem of robot motion planning. The answer is configuration
spaces, that is explained in [18]. One of the main consequence of this innovative
approach to the robot motion planning problem in any configuration space X

Received 18 April 2020 – Accepted 11 July 2020

http://dx.doi.org/10.4995/agt.2020.13553


M. İs and İ. Karaca

is the calculation of the topological complexity TC(X), which depends only on
the homotopy type of X [17].

This numerical invariant plays a crucial role in the selection of the best
suited route for the robot by measuring the navigational complexity of a sys-
tem’s configuration space. The concept of Schwarz genus of a fibration [29] and
some properties of fibrations are united and it follows that a new definition of
the topological complexity TC(X) coincides with the first one. Farber devel-
ops remarkable methods to compute lower or upper bounds for the topological
complexity TC(X) [17]. Using cohomological cup-product is one of the most
precious one from the view of topology. Farber and Grant extend this method
to any cohomology operations [19]. Farber states that the topological com-
plexity TC(X) is greater than the zero-divisor-cup-length of the cohomology
H∗(X; k), where k is a field [Theorem 7,[17]]. In addition, Farber uses Künneth
formulae to prove this theorem. In digital setting, Ege and Karaca introduce
the digital explanation of cup-product and also show that Künneth formulae
does not hold for digital images [15]. We examine in this study that whether
it is valid or not for the digital cup-product or any other digital cohomology
operations. It is important to consider the generalization of the topological
complexity. Rudyak introduced the higher topological complexity TCn(X) in
[28], where X is a path-connected topological space and n is a positive inte-
ger. It is also noted that the higher topological complexity TCn(X) is more
significant for n > 1.

The subject of robotics can gain even more values in the future because
the main areas in which digital topology is influenced are the issues directly
related to the technology of our time such as robot designs, image processing,
computer graphics algorithms and computer images. So Karaca and Is give
the digital version of the topological complexity TC(X) [23]. We will show
that it is also possible to generalize this digital version TC(X, κ), where (X, κ)
is a digital image. To construct the digital higher topological complexity, we
need a good knowledge of digital homotopy theory. Then we sometimes refer
to many articles or books from algebraic topology and digital topology such as
[10], [11], [12], [27], [16], [24], [30], and [31]. We introduce the different version
of some definitions. For example, we do not prefer using subdivisions in the
definition of a cofibration defined in [27].

In this paper, we try to reveal the simple background of digital topology in
the first part. After that we present some new results or reinterpretations about
function spaces, evaluation maps, exponential law, fibrations, and cofibrations
in digital topology using several definitions, in which take part in the same
section, for reaching our main goal that is to give a new definition of the
digital topological complexity. In topological setting, these are facts in the
study of homotopy theory but in digital setting, they must be proved. We
sometimes reinterpret some existing definitions from our own perspective. We
all do it because in Section 4, we want to introduce digital higher topological
complexity via this new definition includes digital fibrations. Also, we show
some properties about the digital higher topological complexity TCn(X, κ).

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 306



The higher topological complexity in digital images

For example, we address when the topological complexity TC coincides with
the higher topological complexity TCn in digital images. Finally, in Section
5, we go back to the study of the digital topological complexity for a short
time. We are interested in a very important tool often used in topological
robotics. It is a cohomological lower bound for the topological complexity TC.
We show that it is invalid for digital images. We give a counter example to
show our assertion in the last.

2. Preliminaries

In this section, we present fundamental notions and some basic facts for
digital topology and topological robotics.

Let Zn be the set of lattice points in the n−dimensional Euclidean space.
Then (X, κ) is called a digital image, where X ⊂ Zn and κ is an adjacency
relation for the elements of X, [4]. Two distinct points p and q in Zn are
cl−adjacent for a positive integer l with 1 ≤ l ≤ n, if there are at most l
indices i such that |pi −qi| = 1 and for all other indices i such that |pi −qi| ∕= 1,
pi = qi, [4]. For instance, consider the situations n = 1, n = 2 and n = 3,
respectively. Then we have 2−adjacency in Z since c1 = 2 in the first case;
4 and 8 adjacencies in Z2 since c1 = 4 and c2 = 8 in the second case and last
6, 18, and 26 adjacencies in Z3 since c1 = 6, c2 = 18 and c3 = 26 as well.

Given the adjacency relation κ on Zn, a κ−neighbor of p ∈ Zn is a point of
Zn that is κ−adjacent to p, [22]. A digital image X ⊂ Zn is κ−connected if and
only if for every pair of different points x, y ∈ X, there is a set {x0, x1, ..., xr}
of points of the digital image X such that x = x0, y = xr and xi and xi+1 are
κ−neighbors, where i = 0, 1, ..., r − 1, [22].

Let X ⊂ Zn0 and Y ⊂ Zn1. Assume that f : X −→ Y is a function and
κi is an adjacency relation defined on Zni, for i = {0, 1}. f is called digitally
(κ0, κ1)−continuous if, when any κ0−connected subset of X is taken, its image
under f is also κ1−connected, [4].

Proposition 2.1 ([4]). Assume that two digital images (X, κ) and (X
′
, λ) are

given. Then the map h : X −→ X
′
is (κ, λ)−continuous if and only if for any

x and x
′
∈ X such that x and x

′
are κ−adjacent, either f(x) = f(x

′
) or f(x)

and f(x
′
) are λ−adjacent.

Proposition 2.2 ([4]). If f : (X, κ1) −→ (Y, κ2) and g : (Y, κ2) −→ (Z, κ3)
are digitally continuous maps, then the composite map

g ◦ f : (X, κ1) −→ (Z, κ3)

is digitally continuous as well.

Let X ⊂ Zn0 and Y ⊂ Zn1 be digital images with κ0−adjacency and
κ1−adjacency, respectively. f : X −→ Y is a digital (κ0, κ1)−isomorphism if
f is bijective and digital (κ0, κ1)−continuous and f−1 : Y −→ X is digital
(κ1, κ0)−continuous, [7].

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 307



M. İs and İ. Karaca

Proposition 2.3 ([3]). A digital isomorphism relation is equivalence on digital
images.

A digital interval is defined by [a, b]Z = {z ∈ Z : a ≤ z ≤ b}, [6]. Let
(X, κ) be a digital image. We say that f is a digital path from x to y in (X, κ)
if f : [0, m]Z −→ X is a (2, κ)−continuous function such that f(0) = x, and
f(m) = y, [6]. If f(0) = f(m), then the κ−path is said to be closed, and the
function f is called a κ−loop.

Let (X, κ0) ∈ Zn0 and (Y, κ1) ∈ Zn1 be two digital images. For two
(κ0, κ1)−continuous functions f, g : X −→ Y , if there is a positive integer m
and a function H : X × [0, m]Z −→ Y such that

• for all x ∈ X, H(x, 0) = f(x) and H(x, m) = g(x);
• for all x ∈ X, Hx : [0, m]Z −→ Y , defined by Hx(t) = H(x, t) for all
t ∈ [0, m]Z, is (2, κ1)−continuous;

• for all t ∈ [0, m]Z, Ht : X −→ Y , defined by Ht(x) = H(x, t) for all
x ∈ X, is (κ0, κ1)−continuous,

they are said to be digitally (κ0, κ1)−homotopic in Y and this is denoted by
f ≃(κ0,κ1) g, [4]. The function H is called a digital (κ0, κ1)−homotopy between
f and g.

Proposition 2.4 ([4]). A digital homotopy relation is equivalence on digitally
continuous functions.

A digitally continuous function f : X −→ Y is digitally nullhomotopic in Y
if f is digitally homotopic in Y to a constant function, [4]. A (κ0, κ1)−continuous
function f from a digital image X to another image Y is a (κ0, κ1)−homotopy
equivalence if there exists a (κ1, κ0)−continuous function g from Y to X such
that g ◦ f is (κ0, κ0)−homotopic to the identity function 1X and f ◦ g is
(κ1, κ1)−homotopic to the identity function 1Y , [5].

A digital image (X, κ) is said to be κ−contractible if its identity map is
(κ, κ)−homotopic to a constant function c for some c0 ∈ X, where the constant
function c : X −→ X is defined by c(x) = c0 for all x ∈ X, [4]. Let (X, κ) and
(A, λ) be two digital images with the inclusion map i : (A, λ) −→ (X, κ). A
is called a digitally κ−retract of the image X if and only if there is a digitally
continuous map r : (X, κ) −→ (A, λ) such that r(a) = a for all a ∈ A, [4].
Then the function r is called a digital retraction of X onto A. The product of
two digital paths defined in [25]: If f : [0, m1]Z −→ X and g : [0, m2]Z −→ X
are digital κ−paths with the condition f(m1) = g(0), then define the product
(f ∗ g) : [0, m1 + m2]Z −→ X by

(f ∗ g)(t) =
!
f(t), t ∈ [0, m1]Z
g(t − m1), t ∈ [m1, m1 + m2].

Adjacency for the cartesian product of any two digital images is defined
in [27]. Let (X, κ) and (Y, λ) be two digital images and consider the cartesian
product X ×Y of these sets. Then X ×Y has the following adjacency relation:
for all x1, x2 ∈ X and y1, y2 ∈ Y , we say that (x1, y1) and (x2, y2) are adjacent

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 308



The higher topological complexity in digital images

on X × Y if x1 and x2 are κ−adjacent and y1 and y2 are λ−adjacent. This
adjacency relation on X × Y is generally denoted by κ∗.

Definition 2.5 ([24]). Let (E, κ1), (B, κ2) and (F, κ3) be any digital im-
ages, where B is a κ2−connected space. Let p : (E, κ1) −→ (B, κ2) be a
(κ1, κ2)−continuous surjection map. Then

• the triple (E, p, B) is called a digital bundle. The digital set B is called
a digital base set, the digital set E is called a digital total set and the
digital map p is called a digital projection of the bundle.

• the quadruple ξ = (E, p, B, F) is called a digital fiber bundle with a
digital base set B, a digital total set E, a digital fiber set F if p satisfies
the following two conditions:
1) For all b ∈ B, the map p−1(b) −→ F is a (κ1, κ3)−isomorphism.
2) For every point b ∈ B, there exists a κ2−connected subset U of
B such that ϕ : p−1(U) −→ U × F is (κ1, κ∗)−isomorphism making
following diagram commute:

p−1(U)
ϕ

!!

p
""
❋❋

❋❋
❋❋

❋❋
❋

U × F.

##①①
①①
①①
①①
①

U

Definition 2.6 ([16]). Let (E, κ1) and (B, κ2) be two digital images.
A digital map p : (E, κ1) −→ (B, κ2) is said to have the homotopy lifting prop-
erty with respect to a digital image (X, κ3) if for any digital map "f : X −→ E
and any digital homotopy G : X×[0, m]Z −→ B such that p◦ "f = G◦i, where i is
an inclusion map and m is a positive integer, there exists a (κ∗, κ0)−continuous
map "G : X × [0, m]Z −→ E making both triangles below commute:

X
!f

!!

i

$$

E

p

$$

X × [0, m]Z
G

!!

!G
%%

B.

Definition 2.7 ([16]). A digital map p : (E, κ1) −→ (B, κ2) is a digital fibration
if it has the homotopy lifting property with respect to every digital image. If
b0 ∈ B, then p−1(b0) = F is called the digital fiber.

Ege and Karaca prove that the composition of two digital fibrations is
again a digital fibration, [16]. They also show that if the digital maps

p1 : (E1, κ1) −→ (B1, κ2) and p2 : (E2, κ
′

1) −→ (B2, κ
′

2) are digital fibrations,
then

p1 × p2 : (E1 × E2, κ∗) −→ (B1 × B2, κ
′

∗)

is a digital fibration, where κ∗ and κ
′

∗ are adjancency relations on cartesian
products (E1 × E2) and (B1 × B2), respectively.

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 309



M. İs and İ. Karaca

Let (X, κ) and (Y, λ) be any digital images. The digital function space Y X

is defined as the set of all digitally continuous functions X −→ Y and has an
adjacency relation as follows, [27]: for all f, g ∈ Y X, the statement x and x

′
are

κ−adjacent on X implies that f(x) and g(x
′
) are λ−adjacent. Given two digi-

tal paths f, g ∈ (X, κ1)([0,m]Z,2), we say that the paths f and g are γ−connected
if for all t times, they are γ−connected, where γ is an adjacency relation on
(X, κ1)

([0,m]Z,2), [23]. Suppose now (Y, κ2) and (Z, κ3) are digital images. Digi-
tal function space map (Z, κ3)

(Y,κ2) is the set of all maps from (Y, κ2) to (Z, κ3)
with an adjacency as follows, [27]: for f, g ∈ (Z, κ3)(Y,κ2), f and g are adjacent
if f(y) and g(y

′
) are κ3−adjacent whenever y and y

′
are κ2−adjacent, for any

y, y
′
∈ (Y, κ2).
We recall something about a digital image PX of all digital paths from

[23]. To construct a digitally continuous digital motion planning algorithm
s : X × X −→ PX, it is needed to be define the digital connectedness on PX
by the definition of the digital continuity. Let χ be an adjacency relation on
the digital image PX. Let also α and β be two digital paths in the digital
image PX. The paths α and β are χ−connected if for all t times, they are
χ−connected, where t ∈ [0, m]Z. It is also noted that if we have different
steps (t times) for the digital paths, then we equalize the number of steps by
increasing the less one of the paths with the endpoint of it. For example, two
paths α = xyzw and β = xy are given in PX. Then we consider β as xyyy
and now we can have an idea that whether α and β are adjacent or not.

Definition 2.8 ([23]). The digital topological complexity TC(X, κ) is the min-
imal number k such that

X × X = U1 ∪ U2 ∪ ... ∪ Uk

with the property that π admits a digitally continuous map sj : Uj −→ PX
such that π ◦ sj = 1 over each Uj ⊂ X × X. If no such k exists, then we will
set TC(X, κ) = ∞.

Karaca and Is state that when the digital image (X, κ) is κ−contractible,
TC(X, κ1) is equal to 1 and the converse of this statement is also true, [23].
In addition, they show that the digital image X with two different adjacencies
κ1 and κ2 yields the result that if κ1 < κ2, then TC(X, κ1) ≥ TC(X, κ2).
Another outstanding statement in [23] is that the digital topological complexity
TC(X, κ) of a digital image (X, κ) is an invariant up to the digital homotopy.

3. Some definitions and properties in the digital homotopy theory

In this section, we give some useful definitions and properties that we need
in the next section. These are commonly related to the homotopy theory in
digital topology.

Definition 3.1. Let f : (X, κ1) −→ (Y, κ2) be a map in digital images with
digitally connected spaces (X, κ1) and (Y, κ2). A digital fibrational substitute

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 310



The higher topological complexity in digital images

of f is defined as a digital fibration #f : (Z, κ3) −→ (Y, κ2) such that there exists
a commutative diagram

X
h
!!

f

$$

Z

"f
$$

Y
1Y

Y,

where h is a digital homotopy equivalence.

Example 3.2. Let X ⊂ Z be a one-point digital image and Y be a digi-
tal image [0, 1]Z × [0, 1]Z ⊂ Z2 with 4−adjacency such that f : X −→ Y
is a digital map. Consider another digital map g : MSS

′

6 −→ Y , where
MSS

′

6 = [0, 1]Z × [0, 1]Z × [0, 1]Z ⊂ Z3 with 6−adjacency. We know that g
is a digital fibration, [16]. Moreover, there is a digital homotopy equivalence

h : X −→ MSS
′

6 because MSS
′

6 is 6−contractible, [21]. Then the commuta-
tivity of the following diagram holds:

X
h
!!

f
&&
❊❊

❊❊
❊❊

❊❊
❊ MSS

′

6

g

$$

Y.

Thus, we conclude that g is a digital fibrational substitute of f.

Lemma 3.3. Any digital map f : (X, κ1) −→ (Y, κ2) has a digital fibrational
substitute.

Proof. Let f : X −→ Y be a digital map. For any m ∈ N, set the digital
image Z = {(x, α) : x ∈ X, α : [0, m]Z −→ Y, α(0) = f(x)}. Let α∗ be the
adjacency relation on the cartesian product digital image X × Y [0,m]Z. α∗ is
defined as follows: for any (x1, α1), (x2, α2) ∈ X × Y [0,m]Z, if x1 and x2 are
adjacent points and α1 and α2 are adjacent paths, then (x1, α1) and (x2, α2)
are adjacent pairs of the elements in the cartesian product image. Z is a subset
of the cartesian product image so the adjacency relation on Z is the same with
the cartesian product. Consider the digital map

g : Z −→ Y
(x, α) .−→ α(1).

We also define h : X −→ Z with h(x) = (x, αx), where αx(t) = f(x) for all
t ∈ [0, m]Z. We first get

g ◦ h(x) = g(x, αx) = gx(1) = f(x).
In order to show that g is a digital fibration, we need to build a new digital map
"G : X × [0, m]Z −→ Z. Let G : X × [0, m]Z −→ Y be a digital homotopy. If we
take "G(x, t) = h(x) and i(x) = (x, t) for t ∈ [0, m]Z, then we have that

"G ◦ i(x) = "G(x, t) = h(x),

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 311



M. İs and İ. Karaca

and

g ◦ "G(x, t) = g ◦ h(x) = G ◦ i(x) = G(x, t)

from g ◦ h = G ◦ i using the definition of a digital fibration. This shows
that g is a digital fibration. Finally, we say that h : X −→ Z is a digital
homotopy equivalence with considering the digital map k : Z −→ X, defined
by k(x, α) = x for any (x, α) ∈ Z. As a consequence, g is a digital fibrational
substitute of f. □

Definition 3.4. Let (E, λ1), (E
′
, λ

′

1), (B, λ2) and (B
′
, λ

′

2) be digital im-
ages. Then a digital map of digital fibrations p : (E, λ1) −→ (B, λ2) to
p

′
: (E

′
, λ

′

1) −→ (B
′
, λ

′

2) is a commutative diagram:

E
!f
!!

p

$$

E
′

p
′

$$

B
f
!! B

′
.

Definition 3.5. Let p : (E, λ1) −→ (B, λ2) be a digital fibration. Two digital
maps f0, f1 : (X, λ3) −→ (E, λ1) are said to be digitally fiber homotopic pro-
vided that there is a digital homotopy F : X × [0, m]Z −→ E between f0 and
f1 such that p ◦ F(x, t) = p ◦ f0(x) for x ∈ X and t ∈ [0, m]Z.

Definition 3.6. Let p1 : (E1, λ1) −→ (B, λ) and p2 : (E2, λ2) −→ (B, λ) be
two digital fibrations. Then they are said to digital fiber homotopy equivalent if
there exist digital maps f : (E1, λ1) −→ (E2, λ2) and g : (E2, λ2) −→ (E1, λ1)
for which g ◦f is digitally fiber homotopic to 1(E1,λ1) and f ◦g is digitally fiber
homotopic to 1(E2,λ2).

Lemma 3.7. Any two digital fibrational substitutes of a digital map
f : (X, κ1) −→ (Y, κ2) are digitally fiber homotopy equivalent fibrations.

Proof. Let f : (X, κ1) −→ (Y, κ2) be a digital map and assume that #f and #g are
two digital fibrational substitutes of it. Then we have the following diagram
consisting of the union of two commutative diagrams;

Z
′

"g
''
❅❅

❅❅
❅❅

❅❅
X

k
((

h
!!

f

$$

Z

"f))%%
%%
%%
%%

Y,

i.e. #f ◦ h = f and #g ◦ k = f. Since both the digital maps h and k on (X, κ1)
are digitally homotopy equivalences, there exist two digitally continuous maps
h1 : (Z, κ3) −→ (X, κ1) and k1 : (Z

′
, κ

′

3) −→ (X, κ1) such that h ◦ h1 ≃(κ3,κ3)
1(Z,κ3), h1 ◦h ≃(κ1,κ1) 1(X,κ1), k1 ◦k ≃(κ1,κ1) 1(X,κ1) and k◦k1 ≃(κ′3,κ′3) 1(Z′ ,κ′3).

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 312



The higher topological complexity in digital images

We want to show that #f and #g are digitally fiber homotopy equivalent fibra-
tions. So we have to guarantee the existence of two digital maps Z −→ Z

′

and Z
′
−→ Z such that their compositions are digitally fiber homotopic to

idendities on Z and Z
′
, respectively. Now, we consider the digital maps

k ◦ h1 : (Z, κ3) −→ (Z
′
, κ

′

3) and h ◦ k1 : (Z
′
, κ

′

3) −→ (Z, κ3). It is easy to
see that

(h ◦ k1) ◦ (k ◦ h1) ≃(κ3,κ3) 1(Z,κ3)
and

(k ◦ h1) ◦ (h ◦ k1) ≃(κ′3,κ′3) 1(Z,κ′3).

We conclude that the two digital fibrational substitutes of f is digitally fiber

homotopy equivalent because #g ◦ (k ◦ h1) = #f and #f ◦ (h ◦ k1) = #g hold by
Definition 3.4. □

Definition 3.8. The digital Schwarz genus of a digital fibration
p : (E, λ1) −→ (B, λ2) is defined as a minimum number k such that

B = U1 ∪ U2 ∪ ... ∪ Uk
with the property that there is a digitally continuous map
si : (Ui, λ1) −→ (E, λ2) for all 1 ≤ i ≤ k, satisfies p ◦ si = 1Ui over each
Ui ⊂ B.

The digital Schwarz genus of a digital map f is defined as the digital
Schwarz genus of the digital fibrational substitute of f.

Lemma 3.9. Let f : (X, κ1) −→ (Y, κ2) and g : (Y, κ2) −→ (Z, κ3) be two
maps. Then the digital Schwarz genus of the map g ◦ f is not less than the
digital Schwarz genus of the map g.

Proof. Let f and g be digital fibrations. Then g ◦ f is a digital fibration. Now
assume that the digital Schwarz genus of the digital map g◦f is k. Then we have
Z = U1∪U2∪...∪Uk such that there exists a digital map sj : (Uj, κ3) −→ (X, κ1)
with (g ◦ f) ◦ sj = 1Uj over each Uj ⊂ Z, where j = 1, 2, ..., k. For each Uj, we
obtain a new digital map tj : (Uj, κ3) −→ (Y, κ2) with tj = f ◦ sj. This implies
that g ◦ tj = g ◦ (f ◦ sj) = 1Uj . It shows that the digital Schwarz genus of the
digital map g does not exceed k because the digital maps tj are constructed by
the digital maps sj. If f and g are not digital fibrations, then we consider the
digital fibrational substitutes of them. Similarly, the digital Schwarz genus of
the digital map g is less than or equal to the the digital Schwarz genus of the
map g ◦ f. □

Definition 3.10. Let (X, κ1) and (Y, κ2) be digital images. Then the digital
map

E
κ1,κ2
X,Y : (Y

X × X, κ∗) −→ (Y, κ2),
defined by E

κ1,κ2
X,Y (f, x) = f(x), is called a digital evaluation map.

Proposition 3.11. The digital evaluation map is a digitally continuous map.

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 313



M. İs and İ. Karaca

Proof. Let (f, x) and (g, x
′
) be two points in the digital image Y X × X such

that they are κ∗−connected. Let λ be an adjacency relation on the set Y X.
By the definition of adjacency for the cartesian product, we have that f and
g are λ−adjacent and x and x

′
are κ1−adjacent. These give us that f(x) and

g(x
′
) are κ2−adjacent. □

Definition 3.12. Let (X, κ1), (Y, κ2) and (Z, κ3) be any three digital images
such that f : (X × Y, κ∗) −→ (Z, κ3) is a digitally continuous map. Then the
digital map

f : (X, κ1) −→ (ZY , λ),
defined by f(x)(y) = f(x, y), is called a digital adjoint map.

Proposition 3.13. If (X, κ1), (Y, κ2) and (Z, κ3) are any three digital images
such that f : (X × Y, κ∗) −→ (Z, κ3) is a digitally continuous map, then the
digital adjoint map

f : (X, κ1) −→ (ZY , λ)
x .−→ f(x)

is also digitally continuous.

Proof. Let x and x
′
be two points in X such that x and x

′
are κ1−adjacent.

Then (x, y) and (x
′
, y) are κ∗−adjacent for any y ∈ Y . Since f is digitally

continuous, we have that f(x, y) and f(x
′
, y) are κ3−adjacent. Hence, f(x)(y)

and f(x
′
)(y) are κ3−adjacent. Consequently, f(x) and f(x

′
) are λ−adjacent.

□

Proposition 3.14. Let (X, κ1), (Y, κ2) and (Z, κ3) be digital images. Then
the map

α : (ZX×Y , κ∗) −→ ((ZY )X, κ)
f .−→ α(f) = f

is digitally continuous, where κ∗ and κ are adjacency relations on Z
X×Y and

(ZY )X, respectively.

Proof. Let f and g be given in ZX×Y such that f and g are κ∗-adjacent and
let λ∗ be an adjacency relation on X × Y . We show that α(f) and α(g)
are κ−adjacent with considering α(f) = f and α(g) = g. Now let x and x

′

be two κ1−adjacent points in X. Then (x, y) and (x
′
, y) are λ∗−adjacent in

X ×Y . Moreover, we see that f(x, y) and g(x
′
, y) are κ3−adjacent. This means

that f(x)(y) and g(x
′
)(y) are κ3−adjacent. Therefore, the result holds from

Proposition 3.13. □

Remark 3.15. A digitally continuous map ϕ : X −→ ZY induces a digital map

ϕ : X × Y −→ Z,

defined by ϕ = E
κ2,κ3
Y,Z ◦ (ϕ × 1Y );

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 314



The higher topological complexity in digital images

X × Y ϕ×1Y−→ ZY × Y
E

κ2,κ3
Y,Z−→ Z.

The composite map E
κ2,κ3
Y,Z ◦ (ϕ × 1Y ) is digitally continuous since E

κ2,κ3
Y,Z ,

ϕ and 1Y are digitally continuous.

Proposition 3.16. Let (X, κ1), (Y, κ2) and (Z, κ3) be any digital images.
Then the map

β : ((ZY )X, κ) −→ (ZX×Y , λ)
ϕ .−→ β(ϕ) = ϕ

is digitally continuous.

Proof. Let ϕ and χ be two κ−adjacent digital maps in (ZY )X, κ∗ an adjacency
relation on X × Y , τ an adjacency relation on ZY and µ an adjaceny relation
on ZY ×Y . We show that ϕ and χ are λ−adjacent in ZX×Y . Now assume that
(x, y) and (x

′
, y

′
) ∈ X ×Y are κ∗−adjacent. Then x and x

′
are κ1−adjacent in

X, so ϕ(x) and χ(x
′
) are τ−adjacent in ZY . Since y and y

′
are κ2−adjacent,

(ϕ × 1Y )(x, y) and (χ × 1Y )(x
′
, y

′
) are µ−adjacent in ZY × Y . By the digital

continuity of the evaluation map E
κ2,κ3
Y,Z and Remark 3.15, the result holds. □

Proposition 3.17. Let (X, κ1), (Y, κ2) and (Z, κ3) be any digital images.
Then the maps α : (ZX×Y , κ∗) → ((ZY )X, κ) and β : ((ZY )X, κ) → (ZX×Y , λ)
are bijective.

Proof. Consider the digital composition maps α◦β : ((ZY )X, κ) → ((ZY )X, κ)
and β ◦ α : (ZX×Y , κ∗) → (ZX×Y , κ∗). Then we have that

α ◦ β(ϕ) = α(β(ϕ)) = α(ϕ) = (ϕ) = ϕ
and

β ◦ α(f) = β(α(f)) = β(f) = (f) = f

for all digitally continuous maps ϕ ∈ (ZY )X and f ∈ ZX×Y . □

We refer to [31] for more details on the topological setting.

Theorem 3.18. If (X, κ1), (Y, κ2) and (Z, κ3) are three digital images, then
the map α : (ZX×Y , λ) −→ ((ZY )X, κ), defined by α(g) = g, is a digital
isomorphism, where λ is an adjacency relation on the digital image ZX×Y and
κ is an adjacency relation on the digital image (ZY )X.

Proof. From Proposition 3.11, E
λ∗,κ3
X×Y,Z is digitally continuous, where λ∗ is an

adjacency relation on X × Y . We can express another version of the digital
image E

λ∗,κ3
X×Y,Z as E

κ2,κ3
Y,Z ◦ (α1 × 1Y ), where α1 = E

κ1,µ
X,ZY

◦ (α × 1X) such that
µ is an adjacency relation on ZY . As a result of Proposition 3.14, Proposition
3.11 and the digital continuity of the identity map, α1 is digitally continuous.
Finally, we conclude that α is digitally continuous.
Conversely, the digitally continuous map E

κ2,κ3
Y,Z ◦(E

κ1,µ
X,ZY

×1Y ) equals the digital
map E

λ∗,κ3
X×Y,Z ◦(α

−1 ×1X×Y ). As a result of Proposition 3.17, Proposition 3.16,

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 315



M. İs and İ. Karaca

Proposition 3.11 and the digital continuity of the identity map, α−1 is digitally
continuous as well. □

Corollary 3.19. Let (Y, λ) be a digital image. Then

µ : (Y [0,n]Z)[0,m]Z −→ (Y [0,m]Z)[0,n]Z,

for m, n ∈ N, is a digital isomorphism.

Proof. Let κ∗ and λ∗ be adjacency relations on the digital images
[0, n]Z × [0, m]Z and [0, m]Z × [0, n]Z, respectively. First, we show that the
digital map

γ : ([0, n]Z × [0, m]Z, κ∗) −→ ([0, m]Z × [0, n]Z, λ∗)

(s, t) .−→ γ(s, t) = (t, s)
is a digital isomorphism for any s ∈ [0, n]Z and t ∈ [0, m]Z.

• To show that γ is injective, let’s define the digital map

δ : ([0, m]Z × [0, n]Z, λ∗) −→ ([0, n]Z × [0, m]Z, κ∗)

with δ(t, s) = (s, t). Since

γ ◦ δ(t, s) = γ(s, t) = (t, s) = 1[0,m]Z×[0,n]Z
and

δ ◦ γ(s, t) = δ(s, x) = (s, t) = 1[0,n]Z×[0,m]Z,

γ has left and right inverses.
• Let (s, t) and (s

′
, t

′
) be two points in [0, n]Z × [0, m]Z such that they

are κ∗−adjacent. Then s and s
′
are 2−adjacent and t and t

′
are

2−adjacent. Hence, we have that (t, s) and (t
′
, s

′
) are λ∗−adjacent.

Since γ(s, t) = (t, s) and γ(s
′
, t

′
) = (t

′
, s

′
), γ is digitally continuous.

• Given two λ∗−adjacent points (t, s) and (t
′
, s

′
) in the digital image

[0, m]Z ×[0, n]Z. This implies that t and t
′
are 2−adjacent and s and s

′

are 2−adjacent at the same time. Thus, we have that (s, t) and (s
′
, t

′
)

are κ∗−adjacent. It shows that γ−1 is digitally continuous because of
that γ−1(t, s) = (s, t) and γ−1(t

′
, s

′
) = (s

′
, t

′
).

After all, we now have that γ is a digital isomorphism and γ defines a digital
map

φ : Y [0,m]Z×[0,n]Z −→ Y [0,n]Z×[0,m]Z

f .−→ φ(f) = f ◦ γ
for any digitally continuous map f in the image Y [0,n]Z×[0,m]Z. Second, we show
that φ is a digital isomorphism.

• To show that φ is bijective, we define a new digital map
ψ : Y [0,n]Z×[0,m]Z −→ Y [0,m]Z×[0,n]Z with ψ(g) = g ◦ γ−1 for any
g ∈ Y [0,n]Z×[0,m]Z. It is easy to see that

ψ ◦ φ(f) = ψ(f ◦ γ) = (f ◦ γ) ◦ γ−1 = f ◦ 1Y [0,n]Z×[0,m]Z = f

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 316



The higher topological complexity in digital images

and

φ ◦ ψ(g) = φ(g ◦ γ−1) = (g ◦ γ−1) ◦ γ = g ◦ 1Y [0,m]Z×[0,n]Z = g.
So φ has left and right inverses.

• The digital continuity of f, g, γ and γ−1 shows that φ and φ−1 are
digitally continuous maps.

By Theorem 3.18, the digital image (Y [0,n]Z)[0,m]Z is digitally isomorphic to
Y [0,m]Z×[0,n]Z and the digital image (Y [0,m]Z)[0,n]Z is digitally isomorphic to
Y [0,n]Z×[0,m]Z. Finally, we conclude that

µ : (Y [0,n]Z)[0,m]Z −→ (Y [0,m]Z)[0,n]Z

is a digital isomorphism because the digital isomorphism relation is an equiva-
lence relation on digital images. □

Definition 3.20. Let (A, τ) and (X, κ) be digital images such that A ⊂ X.
We say that a pair of digital images (X, A) has a digital homotopy extension
property with respect to the digital image (Y, χ) on condition that the digital
map g : X −→ Y and the digital homotopy G : A × [0, m]Z −→ Y , where
m ∈ N, for which g(x) = G(x, 0) for x ∈ A, satisfy that there exists a digital
homotopy

F : X × [0, m]Z −→ Y
with F(x, 0) = g(x) and F |A×[0,m]Z = G for x ∈ X.

Definition 3.21. Let (X
′
, λ) and (X, κ) be two digital images. Then a digital

map f : X
′
−→ X is called a digital cofibration if given two digital maps

g : X −→ Y and G : X
′
× [0, n]Z −→ Y for abritrary digital image Y such that

g ◦ f(x
′
) = G(x

′
, 0) for x

′
∈ X

′
and n ∈ N, then there exists a digital map

F : X × [0, n]Z −→ Y satisfying F(x, 0) = g(x) and F(f(x
′
), t) = G(x

′
, t) for

x ∈ X, x
′
∈ X

′
and t ∈ [0, n]Z.

X
′
× 0 !
"

!!

f×10

$$

X
′
× [0, n]Z

f×1[0,n]Z

$$

G

**&&
&&
&&
&&
&&

Y

X × 0 !
"

!!

g

++①①①①①①①①①
X × [0, n]Z

F

,,

Note that the digital cofibration i : A ↩→ X corresponds to that (X, A)
has the digital homotopy extension property with respect to any digital image.

Proposition 3.22. Let İm = {0, m} and [0, m]Z be two digital images for
m ∈ N. Then the pair ([0, m]Z, İm) has the digital homotopy extension property
if and only if the digital image İm × [0, n]Z ∪ [0, m]Z × 0 is a digital retract of
[0, m]Z × [0, n]Z for n ∈ N.

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 317



M. İs and İ. Karaca

Proof. (⇒) : Suppose that f : İm −→ [0, m]Z is a digital cofibration and choose
the arbitrary digital image Y as İm × [0, n]Z ∪ [0, m]Z ×0 in the Definition 3.21.
Then we have a digital map F : [0, m]Z × [0, n]Z −→ Y . Hence, we can rewrite
F as a retraction

r : [0, m]Z × [0, n]Z −→ İm × [0, n]Z ∪ [0, m]Z × 0.

(⇐) : Let r : [0, m]Z ×[0, n]Z −→ İm ×[0, n]Z ∪[0, m]Z ×0 be a digital retraction.
Assume that g : [0, m]Z −→ Y and G : İm × [0, n]Z −→ Y are digital maps such
that g(a) = G(a, 0) for a ∈ İ. Define a digital map

k : İm × [0, n]Z ∪ [0, m]Z × 0 −→ Y

combining with the maps g and G. Then for all a ∈ İm, s ∈ [0, m]Z and
t ∈ [0, n]Z, the digital homotopy

F : [0, m]Z × [0, n]Z −→ Y
(s, t) .−→ F(s, t) = k(r(s, t))

gives us

F(s, 0) = k(r(s, 0)) = k(s, 0) = g(s),

F(a, t) = k(r(a, t)) = k(a, t) = G(a, t).

Hence, F implies that f : İm −→ [0, m]Z is a digital cofibration. □

Definition 3.23. Let p : (E, λ1) −→ (B, λ2) be a digital map. For n ∈ Z,
define a digital image B = {(e, w) ∈ E × B[O,n]Z : w(0) = p(e)}. There is
a digital map p

′
: E[0,n]Z −→ B defined by p

′
(w) = (w(0), p ◦ w) for any

w : ([0, n]Z, 2) −→ (E, λ1). A digital lifting function of p is a digital map
σ : B −→ E[0,n]Z for which p

′
◦ σ = 1B holds.

The next three propositions and a theorem now guide us to reach our goal
in this section. We first take the advantage of the relation between the digital
lifting function and the digital fibration, and then we charactarize the digital
cofibration. Next, we obtain a new digital fibration using the characterization
of the digital cofibration. As a consequence, we state the final theorem of this
section with the help of these propositions.

Proposition 3.24. Given two digital images (E, λ1) and (B, λ2). Then a
digital map p : (E, λ1) −→ (B, λ2) is a digital fibration if and only if there
exists a digital lifting function σ of p.

Proof. Suppose that p is a digital fibration. Let F : B × [0, m]Z −→ B and
f

′
: B −→ E be digital maps such that F((e, w), t) = w(t) and f

′
(e, w) = e.

Therefore, we have

F((e, w), 0) = w(0) = p(e) = p ◦ f
′
(e, w).

There exists a digital homotopy F
′
: B × [0, m]Z −→ E because p is a digital

fibration. The equalities F
′
((e, w), 0) = f

′
(e, w) and p ◦ F

′
= F hold. By

Theorem 3.18, the map σ : B −→ E[0,m]Z, defined by σ(e, w)(t) = F
′
((e, w), t),

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 318



The higher topological complexity in digital images

is a digital lifting function for the map p. Conversely, let σ be a digital lifting
function for the map p. We take the digital homotopy F : X × [0, m]Z −→ E
and the digital map f

′
: X −→ E such that F(x, 0) = p ◦ f

′
(x). We define

g : X −→ B[0,m]Z by g(x)(t) = F(x, t). So we can construct a map

F
′
: X × [0, m]Z −→ E

(x, t) .−→ F
′
(x, t) = σ(f

′
(x), g(x))(t).

Hence, the equalities F
′
(x, 0) = f

′
(x) and p ◦ F

′
= F hold. As a conclusion,

the map p has the digital homotopy lifting property. □

Consider two digital images İm = {0, m} and [0, m]Z. Let f : İm → [0, m]Z
be a digital map defined by f(0) = 0 and f(m) = m. Define a digital image

[0, m]Z which is the quotient space of the sum (İm × [0, n]Z) ∨ ([0, m]Z × 0)
obtained by identifying (x

′
, 0) ∈ İm × [0, n]Z with (f(x

′
), 0) ∈ [0, m]Z × 0, for

all x
′
∈ İm. Then there exists a digital map

i
′
: ([0, m]Z, τ) −→ ([0, m]Z × [0, n]Z, τ∗),

defined by i
′
[x

′
, t] = (f(x

′
), t), for all t ∈ [0, n]Z and x

′
∈ İm and i

′
[x, 0] = (x, 0)

for all x ∈ [0, m]Z, where τ and τ∗ are adjacency relations for the digital images
[0, m]Z and [0, m]Z × [0, n]Z, respectively.

Proposition 3.25. Let İm = {0, m} and [0, m]Z be two digital images. Assume
that f : İm −→ [0, m]Z is a digital map. Then f is a digital cofibration if and
only if there exists a digital map

ρ : ([0, m]Z × [0, n]Z, τ∗) −→ ([0, m]Z, λ)

such that ρ is a left inverse of the map i
′
.

Proof. (⇒) : Suppose that the digital map f is a digital cofibration and consider
the digital maps g : [0, m]Z −→ [0, m]Z and G : İ × [0, n]Z −→ [0, m]Z with
g(x) = [x, 0] and G(x

′
, t) = [x

′
, t]. We now have that

G(x
′
, 0) = [x

′
, 0] = [f(x

′
), 0] = g ◦ f(x

′
).

Since f is a digital cofibration, we define a digital map

ρ : [0, m]Z × [0, n]Z −→ [0, m]Z
such that ρ(x, 0) = g(x) and ρ(f(x

′
), t) = G(x

′
, t) hold for x ∈ [0, m]Z and

x
′
∈ İ. Due to

ρ ◦ i
′
[x, 0] = ρ(x, 0) = g(x) = [x, 0],

and

ρ ◦ i
′
[x

′
, t] = ρ(f(x

′
), t) = G(f(x

′
), t) = [x

′
, t],

ρ is a left inverse of the map i
′
.

(⇐) : Suppose that ρ : ([0, m]Z × [0, n]Z, κ∗) −→ [0, m]Z is a digital map with
ρ ◦ i

′
= 1

[0,m]Z
and let g : [0, m]Z −→ Y and G : İm × [0, n]Z −→ Y be two

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 319



M. İs and İ. Karaca

digital maps such that G(x
′
, 0) = g ◦ f(x

′
) for x

′
∈ İm. Then there is a digital

map

G : [0, m]Z −→ Y
defined by G[x

′
, t] = G(x

′
, t) and G[x, 0] = g(x) for any t ∈ [0, n]Z. For all

x ∈ [0, m]Z and x
′
∈ İm, we have that

F(x, 0) = G ◦ ρ(x, 0) = G ◦ (ρ ◦ i
′
([x, 0])) = G[x, 0] = g(x),

and

F(f(x
′
), t) = G ◦ ρ(f(x

′
), t) = G ◦ (ρ ◦ i

′
([x, t])) = G[x

′
, t] = G[x

′
, t].

Thus, we obtain that F is a cofibration. □

Proposition 3.26. If the map f : İm −→ [0, m]Z is a digital cofibration, then
the digital map

p : Y [0,m]Z −→ Y İm

g .−→ p(g) = g ◦ f
is a digital fibration.

Proof. Assume that the map f : İm −→ [0, m]Z is a digital cofibration. By
Proposition 3.25, we have that the digital map i

′
: [0, m]Z −→ [0, m]Z × [0, n]Z

has a left inverse σ : [0, m]Z × [0, n]Z −→ [0, m]Z. Define a new digital map
σ

′
: Y [0,m]Z −→ Y [0,m]Z×[0,n]Z with σ

′
(g) = g ◦ σ, where g ∈ Y [0,m]Z. By using

Corollary 3.19, we see that Y [0,m]Z×[0,n]Z is digital isomorphic to the digital

image (Y [0,m]Z)[0,n]Z. Since Y [0,m]Z is digital isomorphic to the digital image

{(g, G) ∈ Y [0,m]Z × (Y İm)[0,n]Z : g ◦ f = G(0)}, we conclude that σ
′
is a digital

lifting function of p from Proposition 3.24. □

We now give a fundamental theorem of this section which is a key for
defining the digital higher topological complexity in the next section.

Theorem 3.27. For a digital image (X, κ1), the digital map

p : X[0,m]Z −→ X × X

w .−→ p(w) = (w(0), w(m))

is a digital fibration.

Proof. For m, n ∈ Z, it is easy to see that {0, m} × [0, n]Z ∪ [0, m]Z × 0 is
a digital retract of [0, m]Z × [0, n]Z. By Proposition 3.22, the pair of digi-
tal images ([0, m]Z, {0, m}) has the digital homotopy extension property, i.e.
i : {0, m} −→ [0, m]Z is a digital cofibration for m ∈ N. Proposition 3.26 also
implies that

X[0,m]Z −→ X{0,m}

w .−→ w ◦ i
is a digital fibration. On the other hand, X{0,m} is digital isomorphic to X ×X

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 320



The higher topological complexity in digital images

via g .→ (g(0), g(m)) for any digital map g : {0, m} −→ X. Therefore, the
digital map

p : X[0,m]Z −→ X × X
w .−→ p(w) = (w(0), w(m))

is a digital fibration for any digital image (X, κ1). □

4. The digital higher topological complexity

In this section we will define higher digital topological complexity and
introduce its properties. Digital topological complexity can be equivalently
introduced as follows.

Definition 4.1. Let (X, κ1) be a connected digital image and
p : X[0,m]Z −→ X × X a digital fibration, defined by p(w) = (w(0), w(1)) for
any w ∈ X[0,m]Z. The digital Schwarz genus of p is called the digital topological
complexity of (X, κ1).

It is clear that Definiton 4.1 is equivalent to Definition 2.8.

Definition 4.2. Let X be any κ-connected digital image. Let Jn be the
wedge of n−digital intervals [0, m1]Z, ..., [0, mn]Z for a positive integer n, where
0i ∈ [0, mi], i = 1, ..., n, are identified. Then the digital higher topological
complexity TCn(X, κ) is defined by the digital Schwarz genus of the digital
fibration

en : X
Jn → Xn

f .−→ (f(m1)1, ..., f(mn)n),
where (mi)k, k = 1, ..., n, denotes the endpoints of the i−th interval for each i.

Theorem 4.3. Let (X, κ) be a digital κ−connected image and n be a positive
integer. Then the following hold:

(1) TC1(X, κ) = 1.
(2) TCn(X, κ) is a homotopy invariant in digital images.
(3) TC2(X, κ) coincides with TC(X, κ).
(4) TCn(X, κ) ≤ TCn+1(X, κ).

Proof. (1) Consider a digital map e1 : X
J1 → X defined by e1(f) = f(11).

Since there is a digitally continuous map s1 : X → XJ1 such that e1 ◦ s1 = 1X,
TC(X, κ) = 1.

(2) The proof is a repeated use of the proof of Theorem 4.1 in [23]. Let X
and Y be digitally homotopy equivalent images with the maps f : X → Y and
g : Y → X. Let f ◦ g be digitally homotopic to 1Y . We first assume that U
is a subset of X × X for which s : U → PX is a digitally continuous motion
planning. Then we define V = (g × g)−1(U) and find a digitally continuous
motion planning α : V → PY . For the TCn version of the proof, we have to
define V as n−copies of (g×g×...×g)−1(U), where U belongs to X×X×...×X
because the range of the digital map en is n−copies of X. We also take digitally
continuous maps s : U −→ XJn and α : V −→ Y Jn since the domain of the

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 321



M. İs and İ. Karaca

digital map en includes the digitally continuous maps defined from any digitally
connected space to Jn.

(3) We first note that en : XJn −→ Xn is a digital fibrational substitute
of the diagonal map of digital images ∆n : X −→ Xn. By Definition 3.1, we
must show that en ◦ h = 1Xn ◦ ∆n. Here we define h : X −→ XJn as a digital
map taking any point x in (X, κ) and turning it into the wedge of digital loops
starting and finishing at x. To say h is a digital homotopy equivalence, we
consider that there exists a digital map g : XJn −→ X, defined by g(β) = β(0)
for any β ∈ XJn, such that g◦h is digitally homotopy equivalent to 1X and h◦g
is digitally homotopy equivalent to 1XJn . Hence, we have en ◦ h = 1Xn ◦ ∆n.
On the other hand, the digital fibration en is digitally homotopy equivalent to
the digital fibration

fn : X
[0,m]Z −→ Xn

α .−→ (α(0), α(1), α(2), ..., α(n − 1)),
where m is a positive integer such that n ≤ m − 1. Since we take the digital
homotopy equivalence h as the digital constant map at x in the digital image
(X, κ), we have fn ◦h = ∆n. As a conclusion, TCn(X, κ) is the digital Schwarz
genus of fn and TC(X, κ) is the digital Schwarz genus of p in Definition 4.1.
Moreover, for n = 2, the digital fibration f2 coincides with p. It shows that
TC2(X, κ) = TC(X, κ).

(4) Assume that TCn+1(X, κ) = r and examine the digital higher topologi-
cal complexity TCn(X, κ). Then the digital Schwarz genus of the digital map
en+1 equals r. So we have that X

n+1 = U1 ∪ U2 ∪ ... ∪ Ur and there exists
si : Ui −→ XJn+1 such that en+1 ◦ si = 1Ui for each i ∈ [1, r]. Consider the
digital map an : X

Jn+1 −→ XJn that takes the set of n + 1 paths and deletes
the last one into the set of first n paths. Now choose a point a ∈ X and es-
tablish a new digital map bn : X

n −→ Xn+1 that assigns n points of X to the
n + 1 points of it by adding a to the end of the n points. Last, we set

Vi = {(x1, x2, ..., xn) ∈ Xn : (x1, x2, ..., xn, a) ∈ Ui} ⊂ Xn.
Therefore, we obtain ti = an ◦ si ◦ bn : Vi −→ XJn with the help of the digital
map si such that en ◦ ti = 1Vi for i = 1, 2, ..., r. It shows that the digital
Schwarz genus of en can be at most r and so TCn(X, κ) ≤ r. □

We currently finalize this section with an example about frequently used
the digital surface MSS18 and the digital curve MSC8 in digital topology, [21].

Example 4.4. Consider the minimal simple surface MSS18 = {ai}9i=0 in Z3,
where

a0 = {0, 0, 0}, a1 = {1, 1, 0}, a2 = {0, 1, −1},
a3 = {0, 2, −1}, a4 = {1, 2, 0}, a5 = {0, 3, 0},
a6 = {−1, 2, 0}, a7 = {0, 2, 1}, a8 = {0, 1, 1}, a9 = {−1, 1, 0}.

It is shown that any loop is 18−contractible in MSS18, [9] and
cat18(MSS18) = 1, [2]. By [23, Theorem 5.1], we have TC(MSS18, 18) ≥ 1

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 322



The higher topological complexity in digital images

but [23, Corollary 3.3]] says that TC(MSS18, 18) cannot be greater than 1.
Therefore, we conclude that TC1(MSS18, 18) = 1, TC2(MSS18, 18) = 1 and
TCn(MSS18) ≥ 1, for n ≥ 3, from Theorem 4.3.
On the other hand, if we consider the minimal simple closed curve
MSC8 = {bi}5i=0 in Z2, where

b0 = {0, 0}, b1 = {−1, 1}, b2 = {−1, 2},
b3 = {0, 3}, b4 = {1, 2}, b5 = {1, 1},

then we have TC(MSC8, 8) = 2 by [23, Theorem 3.5]]. It shows that
TC1(MSC8, 8) = 1, TC2(MSC8, 8) = 2 and TCn(MSC8, 8) ≥ 2, for n ≥ 3,
from Theorem 4.3.

5. A different result for the digital topological complexity

Cohomological lower bounds are not valid for the digital topological com-
plexity TC(X, κ), where (X, κ) is a digital image. Let us explain it with an
example.

Example 5.1. Let F be a field. Consider the two same digital images
X = Y = [0, m]Z with 2−adjacency for any m ∈ N and assume that coho-
mological lower bounds are holds in digital images. We know

H∗,2(X; F) = H∗,2(Y ; F) =

!
F , n = 0

0 , n ∕= 0,

and

H∗,4(X × Y ; F) =
!
F , n = 0, 1

0 , n ∕= 0, 1,

from [14] and [1], respectively. Since X and Y are 2−contractible, we have that
TC(X, 2) = 1 = TC(Y, 2). So the zero-divisor-cup-lengths of H∗,2(X; F) and
H∗,2(Y ; F) must be equal to zero. Moreover, TC(X×Y, 4) = 1 because X×Y is
4−contractible. This implies that the zero-divisor-cup-length of H∗,4(X×Y ; F)
is equal to zero as well. On the other hand, the zero-divisor-cup-lengths of
H1,2(X; F) and H1,2(Y ; F) are equal to zero by H1,2(X; F) = H1,2(Y ; F) = 0.
In addition to this, the zero-divisor-cup-length of H1,4(X×Y ; F) is greater than
or equal to 1. We can choose a nonzero fundamental class u ∈ H1,4(X × Y ; F)
such that u = 1 ⊗ u − u ⊗ 1 is a zero-divisor by H1,4(X × Y ; F) = F . We
focus on the first dimension of digital cohomologies with considering that the
minimum adjacency is 4 for X × Y because it is a digital image in Z2. Then
we get a contradiction!

6. Conclusion

This study introduces the theory of higher topological complexity in digi-
tal images. We first start with establishing the homotopy background for this.
As a continuation, we deal with the number of digital topological complexities.

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 323



M. İs and İ. Karaca

Furthermore, we answer the open problem given in the conclusion section of
[23]. We offer a clear solution in digital setting to the question of what relation-
ship between the digital cohomological cup-product and the digital topological
complexity TC(X, κ) will have. Our answer is negative, i.e. it is not suitable
to build such a cohomological structure in digital topology. We can study on
the various areas with different examples. One open problem is to find a re-
lation between TCn and digital Lusternik-Schnirelmann category cat which is
introduced in [2].

Acknowledgements. The authors are thankful to the anonymous referees for
their valuable comments and suggestions. The first author is granted as fellow-
ship by the Scientific and Technological Research Council of Turkey TUBITAK-
2211-A. In addition, this work was partially supported by Research Fund of the
Ege University (Project Number: FDK-2020-21123)

References

[1] H. Arslan, I. Karaca and A. Oztel, Homology groups of n− dimensional digital images,
XXI Turkish National Mathematics Symposium (2008); B1-13.

[2] A. Borat and T. Vergili, Digital lusternik-schnirelmann category, Turkish J. Math. 42,
no.4 (2018), 1845–1852.

[3] L. Boxer, Digitally continuous functions, Pattern Recognit. Lett. 15 (1994), 833–839.
[4] L. Boxer, A classical construction for the digital fundamental group, J. Math. Im. Vis.

10 (1999), 51–62.
[5] L. Boxer, Properties of digital homotopy, J. Math. Im. Vis. 22 (2005), 19–26.
[6] L. Boxer, Homotopy properties of sphere-like digital images, J. Math. Im. Vis. 24 (2006),

167–175.
[7] L. Boxer, Digital products, wedges, and covering spaces. J. Math. Im. Vis. 25 (2006),

169–171.
[8] L. Boxer and I. Karaca, Fundamental groups for digital products, Adv. Appl. Math. Sci.

11, no. 4 (2012), 161–180.
[9] L. Boxer and P. C. Staecker, Fundamental groups and Euler characteristics of sphere-like

digital images, Appl. Gen. Topol. 17, no.2 (2016), 139–158.
[10] L. Chen and J. Zhang, Digital manifolds: an intuitive definition and some properties,

Proceedings of the Second ACM/SIGGRAPH Symposium on Solid Modeling and Ap-
plications (1993), 459–460.

[11] L. Chen, Discrete surfaces and manifolds: a theory of digital-discrete geometry and
topology, Rockville, MD, Scientific & Practical Computing, 2004.

[12] L. Chen and Y. Rong, Digital topological method for computing genus and the betti
numbers, Topol. Appl. 157, no. 12 (2010), 1931–1936.

[13] A. Dranishnikov, Topological complexity of wedges and covering maps, Proc. Amer.
Math. Soc. 142, no. 12 (2014), 4365–4376.

[14] O. Ege and I. Karaca, Fundamental properties of simplicial homology groups for digital
images, Am. J. Comp. Tech. Appl. 1 (2013), 25–43.

[15] O. Ege and I. Karaca, Cohomology theory for digital images, Romanian J. Inf. Sci. Tech.
16, no.1 (2013), 10–28.

[16] O. Ege and I. Karaca, Digital fibrations, Proc. Nat. Academy Sci. India Sec. A, 87
(2017), 109–114.

[17] M. Farber, Topological complexity of motion planning, Discrete Comput. Geom. 29,
(2003), 211-221.

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 324



The higher topological complexity in digital images

[18] M. Farber, Invitation to Topological Robotics. Zur. Lect. Adv. Math., EMS, 2008.
[19] M. Farber and M. Grant, Robot motion planning, weights of cohomology classes, and

cohomology operations, Proc. Amer. Math. Soc. 136, no.9 (2008), 3339–3349.
[20] M. Farber, S. Tabachnikov and S. Yuzvinsky, Topological robotics: motion planning in

projective spaces, Int. Math. Res. Not. 34, (2003), 1850–1870.
[21] S. E. Han, Digital fundamental group and Euler characteristic of a connected sum of

digital closed surfaces, Inf. Sci. 177 (2007), 3314–3326.
[22] G. T. Herman, Oriented surfaces in digital spaces, CVGIP: Graph. Models Im. Proc. 55

(1993), 381–396.
[23] I. Karaca and M. Is, Digital topological complexity numbers, Turkish J. Math. 42, no.

6 (2018), 3173–3181.
[24] I. Karaca and T. Vergili, Fiber bundles in digital images, Proceeding of 2nd International

Symposium on Computing in Science and Engineering 700, no. 67 (2011), 1260–1265.
[25] E. Khalimsky, Motion, deformation, and homotopy in finite spaces. Proceedings IEEE

International Conference on Systems, Man, and Cybernetics (1987), 227–234.
[26] T. Y. Kong, A digital fundamental group, Comp. Graph. 13 (1989), 159–166.
[27] G. Lupton, J. Oprea and N. Scoville, Homotopy theory on digital topology, (2019),

arXiv:1905.07783[math.AT].
[28] Y. Rudyak, On higher analogs of topological complexity, Topol. Appl 157, no. 5 (2010),

916–920.
[29] A. S. Schwarz, The genus of a fiber space, Amer. Math. Soc. Transl. 55, no. 2 (1966),

49–140.
[30] E. Spanier, Algebraic Topology. New York, USA, McGraw-Hill, 1966.
[31] T. tom Dieck, Algebraic Topology, Zurich, Switzerland: EMS Textbooks in Mathema-

tics, EMS, 2008.

c© AGT, UPV, 2020 Appl. Gen. Topol. 21, no. 2 325