A formula for the number of weak endomorphisms on paths
A weak endomorphisms of a graph is a mapping on the vertex set of the graph which preserves or contracts edges. In this paper we provide a formula to determine the cardinalities of weak endomorphism monoids of finite undirected paths.
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2018
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/188413 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | A formula for the number of weak endomorphisms on paths / U. Knauer, N. Pipattanajinda // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 270–279. — Бібліогр.: 5 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188413 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1884132023-02-28T01:27:06Z A formula for the number of weak endomorphisms on paths Knauer, U. Pipattanajinda, N. A weak endomorphisms of a graph is a mapping on the vertex set of the graph which preserves or contracts edges. In this paper we provide a formula to determine the cardinalities of weak endomorphism monoids of finite undirected paths. 2018 Article A formula for the number of weak endomorphisms on paths / U. Knauer, N. Pipattanajinda // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 270–279. — Бібліогр.: 5 назв. — англ. 1726-3255 2010 MSC: 05C30; 05C38. http://dspace.nbuv.gov.ua/handle/123456789/188413 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
A weak endomorphisms of a graph is a mapping on the vertex set of the graph which preserves or contracts edges. In this paper we provide a formula to determine the cardinalities of weak endomorphism monoids of finite undirected paths. |
| format |
Article |
| author |
Knauer, U. Pipattanajinda, N. |
| spellingShingle |
Knauer, U. Pipattanajinda, N. A formula for the number of weak endomorphisms on paths Algebra and Discrete Mathematics |
| author_facet |
Knauer, U. Pipattanajinda, N. |
| author_sort |
Knauer, U. |
| title |
A formula for the number of weak endomorphisms on paths |
| title_short |
A formula for the number of weak endomorphisms on paths |
| title_full |
A formula for the number of weak endomorphisms on paths |
| title_fullStr |
A formula for the number of weak endomorphisms on paths |
| title_full_unstemmed |
A formula for the number of weak endomorphisms on paths |
| title_sort |
formula for the number of weak endomorphisms on paths |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188413 |
| citation_txt |
A formula for the number of weak endomorphisms on paths / U. Knauer, N. Pipattanajinda // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 270–279. — Бібліогр.: 5 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT knaueru aformulaforthenumberofweakendomorphismsonpaths AT pipattanajindan aformulaforthenumberofweakendomorphismsonpaths AT knaueru formulaforthenumberofweakendomorphismsonpaths AT pipattanajindan formulaforthenumberofweakendomorphismsonpaths |
| first_indexed |
2025-07-16T10:26:48Z |
| last_indexed |
2025-07-16T10:26:48Z |
| _version_ |
1837798899427835904 |
| fulltext |
“adm-n4” — 2019/1/24 — 10:02 — page 270 — #120
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 26 (2018). Number 2, pp. 270–279
c© Journal “Algebra and Discrete Mathematics”
A formula for the number of weak
endomorphisms on paths
Ulrich Knauer and Nirutt Pipattanajinda
Communicated by V. Mazorchuk
Abstract. A weak endomorphisms of a graph is a mapping
on the vertex set of the graph which preserves or contracts edges.
In this paper we provide a formula to determine the cardinalities of
weak endomorphism monoids of finite undirected paths.
Introduction and preliminaries
The motivation of this paper has come from [1], where Arworn gives
an algorithm to determine the cardinalities of endomorphism monoids of
finite undirected paths by using the square lattices. Furthermore, in [2],
Arworn and Kim find the number of path homomorphisms by the lattices
and the generalized catalan number, and in [5], Sirisathianwatthana and
Pipattanajinda find the number of cycle weak homomorphisms.
Consider finite simple graphs G with the vertex set V (G) and the
edge set E(G). Let G and H be two graphs. A map f : V (G) → V (H)
is a homomorphism if f preserves the edges, i.e., if {f(x), f(y)} ∈ E(H)
whenever {x, y} ∈ E(G). Further, in [3], a map f : V (G) → V (H) is called
a weak homomorphism (also called egamorphism in [4]) if f preserves or
contracts the edges, i.e., if f(x) = f(y) or {f(x), f(y)} ∈ E(H) whenever
{x, y} ∈ E(G). A (weak) homomorphism from G to itself is called a
(weak) endomorphism of G. Denote the set of (weak) endomorphisms of
2010 MSC: 05C30; 05C38.
Key words and phrases: path, weak endomorphisms, three-dimensional square
lattices.
“adm-n4” — 2019/1/24 — 10:02 — page 271 — #121
U. Knauer, N. Pipattanajinda 271
G by End(G) (WEnd(G)). Clearly End(G) and WEnd(G) form monoids
by composition of mappings. Let Pn = {0, 1, 2, . . . , n − 1} be an undi-
rected path of length n − 1, where n > 1. Denote the number of weak
endomorphisms of the path Pn by |WEnd(Pn)|, and the number of weak
endomorphisms of the path Pn which maps 0 to j by |WEndj(Pn)|.
Let n be a positive integer, the multinomial coefficient is
(
n
r1, r2, . . . , rk
)
=
n!
r1!r2! . . . rk!
(1)
where n = r1 + r2 + · · · + rk and k ∈ Z+. The next result is well-know
and extends Formula (1)
(
n
r1, r2, . . . , rk
)
=
(
n− 1
r1 − 1, r2, . . . , rk
)
+
(
n− 1
r1, r2 − 1, . . . , rk
)
+ · · ·+
(
n− 1
r1, r2, . . . , rk − 1
)
.
(2)
Next, we use the multinomial coefficient (1) and the extended formula
(2) to find all shortest paths on three-dimensional square lattice.
Consider three-dimensional square lattices M(i, j, k) in Figure 1 and
r-ladder three-dimensional square lattices Mr(i, j, k) in Figure 2 (here we
choose i = 6, j = 5, k = 4 and r = 2),
Figure 1 Figure 2
The shortest path on this three-dimensional square lattice from the
point (0, 0, 0) to any point (i, j, k) can be obtained by going from the point
(0, 0, 0) to the point (i, j, k) by (1, 0, 0) or (0, 1, 0) or (0, 0, 1) and similarly
for the next steps. And more generally from (i0, j0, k0) to (i0 + 1, j0, k0)
or (i0, j0 + 1, k0) or (i0, j0, k0 + 1).
“adm-n4” — 2019/1/24 — 10:02 — page 272 — #122
272 Formula for the number of weak endomorphisms
Proposition 1. The numbers M(i, j, k) and Mr(i, j, k) (r < j) of shortest
paths from the point (0, 0, 0) to any point (i, j, k) in the three-dimensional
square lattice and in the r-ladder three-dimensional square lattice are
M(i, j, k) =
(
i+ j + k
i, j, k
)
,
and
Mr(i, j, k) = M(i, j, k)−M(j − r − 1, i+ r + 1, k)
=
(
i+ j + k
i, j, k
)
−
(
i+ j + k
j − r − 1, i+ r + 1, k
)
,
respectively.
Proof. By using (1), (2) and induction.
1. The number of weak endomorphisms on paths
In this section, we give an algorithm for the numbers of weak endo-
morphisms on paths by using the three-dimensional square lattice and
the r-ladder three-dimensional square lattice.
In Figure 3, the possible weak endomorphisms of the path P4 which
map 0 to 0, i.e. the elements of WEnd0(P4) are indicated. There the
numbers in the top line the elements of the domain and the numbers in
the left column denote the elements of the image set.
Figure 3 Figure 4
Take the mapping f ∈ WEnd0(P4) with f(0) = f(1) = f(3) = 0 and
f(2) = 1, symbolized by the upper sequence of dashed arrows. Now we
“adm-n4” — 2019/1/24 — 10:02 — page 273 — #123
U. Knauer, N. Pipattanajinda 273
model this mapping by a shortest path in the 3-dimensional square lattice
as follows: such that f(0) and f(x) is (0, 0, 0) and (i, j, k), respectively for
some x ∈ X = {0, 1, 2, 3}. Now we go from (i, j, k) to (i+1, j, k), (i, j+1, k)
or (i, j, k+1), if f(x+1) = f(x)+1, f(x+1) = f(x)−1 or f(x+1) = f(x),
respectively. So f is represented in the 3-dimensional square lattice by
a shortest path from (0, 0, 0) to (1, 1, 1), compare Figure 4. Hence, the
cardinality |WEnd0(P4)| is the summation of M(i, j, k) and Mr(i, j, k)
where i+ j + k = 3.
So, by Figure 4 and Proposition 1, we get
|WEnd0(P4)| = M(3, 0, 0) +M0(2, 1, 0) +M(2, 0, 1) +M0(1, 1, 1)
+M(1, 0, 2) +M(0, 0, 3)
=
(
3
3, 0, 0
)
+
(
3
2, 1, 0
)
−
(
3
0, 3, 0
)
+
(
3
2, 0, 1
)
+
(
3
1, 1, 1
)
−
(
3
0, 2, 1
)
+
(
3
1, 0, 2
)
+
(
3
0, 0, 3
)
= 13.
Similarly to Figure 3 and Figure 4, in Figure 5 the possible weak endo-
morphisms of the path P4 which map 0 to 1, i.e. the elements of WEnd1(P4)
are symbolized. This implies that the cardinality |WEnd1(P4)| is the sum-
mation of M(i, j, k) and Mr(i, j, k) where i+ j + k = 3, see Figure 6.
Figure 5 Figure 6
So, by Figure 6 and Proposition 1, we get
|WEnd1(P4)| = M(2, 1, 0) +M1(1, 2, 0) +M(2, 0, 1) +M(1, 1, 1)
“adm-n4” — 2019/1/24 — 10:02 — page 274 — #124
274 Formula for the number of weak endomorphisms
+M(1, 0, 2) +M(0, 1, 2) +M(0, 0, 3)
=
(
3
2, 1, 0
)
+
(
3
1, 2, 0
)
−
(
3
0, 3, 0
)
+
(
3
2, 0, 1
)
+
(
3
1, 1, 1
)
+
(
3
1, 0, 2
)
+
(
3
0, 1, 2
)
+
(
3
0, 0, 3
)
= 21.
The next Proposition is as follows:
Proposition 2. Let n be positive integer and j non-negative integer such
that j < n. Then
(1) |WEndj(Pn)| = |WEndn−j−1(Pn)|,
(2) |WEnd(P2n)| = 2
∑n−1
j=0 |WEndj(P2n)|,
(3) |WEnd(P2n+1)| = 2
∑n−1
j=0 |WEndj(P2n+1)|+ |WEndn(P2n+1)|.
Instead of a proof we look again at P4. We use Proposition 2(1), Figures
4, 6 and Proposition 1, to get that |WEnd0(P4)| = |WEnd3(P4)| = 13 and
|WEnd1(P4)| = |WEnd2(P4)| = 21. Thus, |WEnd(P4)| = 2(13+21)=68.
Next, we introduce the following notations:
eM(i, j) :=
i
∑
i0=0
j
∑
j0=0
M(i− i0, j − j0, i0 + j0), (3)
eMr(i, j) :=
i−j+r
∑
i0=0
Mr(i− i0, j, i0). (4)
Further, the eMr(i, j) = 0 if i− j + r < 0 call this (2.3). Thus, in the
example of P4, |WEnd0(P4)| = eM(3, 0)+ eM0(2, 1) and |WEnd1(P4)| =
eM(2, 1) + eM1(1, 2).
First we prove an auxiliary result:
Proposition 3. Let n be positive integer and j non-negative integer such
that j < n
2 − 1. Then
|WEndj(Pn)| =
i
∑
i0=0
j
∑
j0=0
(
n− 1
i− i0, j − j0, i0 + j0
)
+
n
∑
s=1
[
i−2s
∑
i0=0
[
(
n− 1
i− s− i0, j + s, i0
)
−
(
n− 1
s− 1, n− s− i0, i0
)
]
“adm-n4” — 2019/1/24 — 10:02 — page 275 — #125
U. Knauer, N. Pipattanajinda 275
+
j−2s
∑
j0=0
[
(
n− 1
j − s− j0, i+ s, j0
)
−
(
n− 1
s− 1, n− s− j0, j0
)
]]
,
where n− 1 = i+ j.
Proof. Let i = n − j − 1. To find |WEndj(Pn)|, we compute according
to the following Figure 7, drawn for n = 12, j = 5: where in particular
i = 6, t = ⌊ i
2⌋ = 3, t′ = ⌊ j2⌋ = 2, and s = 1, 2, 3,
Figure 7
Thus,
|WEndj(Pn)| = eM(i, j) +
n
∑
s=1
eMj(i− s, j + s) +
n
∑
s=1
eMi(j − s, i+ s),
since eMj(i− s, j + s) = eMi(j − s, i+ s) = 0 if s > n (we observe that
eMj(i − s, j + s) = 0 and eMi(j − s, i + s) = 0 if s > ⌊ i
2⌋ and s > ⌊ j2⌋,
respectively). Equations (3), (4) and Proposition 1, imply that
eM(i, j) =
i
∑
i0=0
j
∑
j0=0
M(i− i0, j − j0, i0 + j0),
=
i
∑
i0=0
j
∑
j0=0
(
n− 1
i− i0, j − j0, i0 + j0
)
,
n
∑
s=1
eMj(i− s, j + s) =
n
∑
s=1
[
i−2s
∑
i0=0
Mj(i− s− i0, j + s, i0)
]
=
n
∑
s=1
[
i−2s
∑
i0=0
[
(
n− 1
i− s− i0, j + s, i0
)
−
(
n− 1
s− 1, n− s− i0, i0
)
]]
,
“adm-n4” — 2019/1/24 — 10:02 — page 276 — #126
276 Formula for the number of weak endomorphisms
n
∑
s=1
eMi(j − s, i+ s) =
n
∑
s=1
[
j−2s
∑
j0=0
Mi(j − s− j0, i+ s, j0)
]
=
n
∑
s=1
[
j−2s
∑
j0=0
[
(
n− 1
j − s− j0, i+ s, j0
)
−
(
n− 1
s− 1, n− s− j0, j0
)
]]
.
Therefore,
|WEndj(Pn)| =
i
∑
i0=0
j
∑
j0=0
(
n− 1
i− i0, j − j0, i0 + j0
)
+
n
∑
s=1
[
i−2s
∑
i0=0
[
(
n− 1
i− s− i0, j + s, i0
)
−
(
n− 1
s− 1, n− s− i0, i0
)
]
+
j−2s
∑
j0=0
[
(
n− 1
j − s− j0, i+ s, j0
)
−
(
n− 1
s− 1, n− s− j0, j0
)
]]
.
Now we can prove the final result.
Theorem 1. Let n be positive integer and j non-negative integer such
that j < n. Then
(1) |WEnd(P2n)| = 2
n−1
∑
j=0
[
eM(i, j) +
2n
∑
s=1
[
eMj(i− s, j + s)
+ eMi(j − s, i+ s)
]
]
, where i = 2n− j − 1,
(2) |WEnd(P2n+1)| = 2
n−1
∑
j=0
[
eM(i, j) +
2n+1
∑
s=1
[
eMj(i− s, j + s)
+ eMi(j − s, i+ s)
]
]
+ eM(n, n)
+ 2
2n+1
∑
s=1
eMn(n− s, n+ s), where i = 2n− j,
where
eM(i, j) =
i
∑
i0=0
j
∑
j0=0
M(i− i0, j − j0, i0 + j0)
and
eMr(i, j) =
i−j+r
∑
i0=0
Mr(i− i0, j, i0).
“adm-n4” — 2019/1/24 — 10:02 — page 277 — #127
U. Knauer, N. Pipattanajinda 277
Proof. (1) This is obvious by Proposition 2(2) and Proposition 3.
(2) From Proposition 2(3),
|WEnd(P2n+1)|
= 2
n−1
∑
j=0
[
eM(i, j) +
2n+1
∑
s=1
[
eMj(i− s, j + s) + eMi(j − s, i+ s)
]
]
+ |WEndn(P2n+1)|,
where i = 2n− j.
Consider j = n. Then i = n. Thus
|WEndn(P2n+1)|
= eM(n, n) +
2n+1
∑
s=1
[
eMn(n− s, n+ s) + eMn(n− s, n+ s)
]
= eM(n, n) + 2
2n+1
∑
s=1
eMn(n− s, n+ s).
2. A sketched extension to homomorphisms from paths
Now we develop a method how to extend the obtained results to
homomorphisms starting from a path to certain lexicographic products
with this path.
We recall, the lexicographic product G[H] of two graphs G and H
has vertex set V (G) × V (H) and {(x1, y1), (x2, y2)} ∈ E(G[H]) when-
ever {x1, x2} ∈ E(G), or x1 = x2 and {y1, y2} ∈ E(H). Consider the
behaviours of the homomorphism from Pn to Pn[Km] where Km denotes
the complete graph with the vertex set V (Km) = {k1, k2, . . . , km}, and of
the homomorphism from Pn to Pn[Cm] where Cm denotes the cycle of
length m− 1 with the vertex set V (Cm) = {0, 1, . . . ,m− 1},m > 3.
Take f ∈ Hom(Pn, Pn[K2]) such that f(i) = (j, k1) where i, j ∈ V (Pn)
and k1 ∈ V (K2). Then f(i+1) ∈ {(j, k2), (j+1, k1), (j−1, k1)}, if j−1, j+
1 ∈ V (Pn). So, for each f : V (Pn) → V (Pn[K2]), define g : V (Pn) → V (Pn)
by g(i) = j if f(i) = (j, kx); kx ∈ V (K2). Then g ∈ WEndi(Pn) whenever
f ∈ Hom(i,kx)(Pn, Pn[K2]), i.e. f ∈ Hom(Pn, Pn[K2]) which map 0 to
(i, kx) for all kx ∈ V (K2). Hence, |Hom(Pn, Pn[K2])| = 2|WEnd(Pn)|.
Thus by Theorem 1, we get the cardinality |Hom(Pn, Pn[K2])|.
This way, for each f ∈ Hom(j,kx)(Pn, Pn[K2]) is the shortest path on
this 3-dimensional square lattice from the point (0, 0, 0) to some point
(i, j1, j2) (and some r-ladder square lattice).
“adm-n4” — 2019/1/24 — 10:02 — page 278 — #128
278 Formula for the number of weak endomorphisms
Consider an (m + 1)-dimensional square lattice M(i, j1, j2, . . . , jm)
and an r-ladder (m+ 1)-dimensional square lattice Mr(i, j1, j2, . . . , jm).
The shortest path on the (m + 1)-dimensional square lattice from the
point (0, 0, 0, . . . , 0) to any point (i, j1, j2, . . . , jm) can be obtained by
going from the point (0, 0, 0, . . . , 0) to the point (i, j1, j2, . . . , jm) by
(i0, j01, j02, . . . , j0m) together with (i0 + 1, j01, j02, . . . , j0m), (i0, j01 + 1,
j02, . . . , j0m), (i0, j01, j02+1, . . . , j0m), . . . , (i0, j01, j02, . . . , j0m+1). Using
(1), (2) and induction, we get the next proposition.
Proposition 4. The numbers
M(i, j1, j2, . . . , jm) and Mr(i, r +m, j2, . . . , jm) (j1 = r +m)
of shortest paths from the point (0, 0, . . . , 0) to any point (i, j1, j2, . . . , jm)
in the (m + 1)-dimensional square lattice and in the r-ladder (m + 1)-
dimensional square lattice is
M(i, j1, j2, . . . , jm) =
(
i+ j1 + j2 + . . .+ jm
i, j1, j2, . . . , jm
)
,
and
Mr(i, r +m, j2, . . . , jm) =
(
i+ j1 + j2 + . . .+ jm
i, j1, j2, . . . , jm
)
−
(
i+ j1 + j2 + . . .+ jm
m− 1, r + i+ 1, j2, . . . , jm
)
,
respectively.
Let f ∈ Hom(Pn, Pn[Km]) such that f(i) = (j, kx) where i, j ∈ V (Pn)
and kx ∈ V (Km). Then f(i+ 1) ∈ {(j, k1), (j, k2), . . . , (j, kx−1), (j, kx+1),
(j, kx+2), . . . , (j, km)} ∪ {(j + 1, kx), (j − 1, kx)}, if j − 1, j + 1 ∈ V (Pn).
We can use the same technique for homomorphism from Pn to Pn[K2]
to get for each f ∈ Hom(j,kx)(Pn, Pn[Km]) the shortest path on this
(m+ 1)-dimensional square lattice from the point (0, 0, 0, . . . , 0) to some
point (i, j1, j2, . . . , jm) (and the r-ladder square lattice). Further, take
f ∈ Hom(Pn, Pn[Cm]) such that f(i) = (j, k) where i, j ∈ V (Pn) and
k ∈ V (Cm). Then f(i+1) ∈ {(j, k− 1), (j, k+1)}∪{(j+1, k), (j− 1, k)},
if j−1, j+1 ∈ V (Pn) and k−1 = m−1, k+1 = 0 for k = 0 and k = m−1,
respectively. Then for each f ∈ Hom(j,k)(Pn, Pn[Cm]) we get the shortest
path on this 4-dimensional square lattice from the point (0, 0, 0, 0) to some
point (i, j1, j2, j4) (and the r-ladder square lattice). So, the algorithms for
the numbers of homomorphisms from the path Pn to the lexicographic
products Pn[Km] and Pn[Cm] can be found.
“adm-n4” — 2019/1/24 — 10:02 — page 279 — #129
U. Knauer, N. Pipattanajinda 279
Acknowledgement
The authors would like to thank Prof. Dr. Srichan Arworn for the help
and the encouragement that she provided in the preparation of this paper.
The work was partially supported by the Research and Development
Institute and the Faculty of Sciences and Technology, Kamphaeng Phet
Rajabhat University, Kamphaeng Phet, Thailand.
References
[1] Sr. Arworn, An algorithm for the numbers of endomorphisms on paths (DM13208),
Discrete Mathematics 309, (2009), 94-103.
[2] Sr. Arworn, Y. Kim, The number of path homomorphisms by the generalized catalan
number, Advances and Applications in Discrete Mathematics 9, (2012)(2), 93-105.
[3] W. Imrich, S. Klavžar, Product Graphs, Wiley, 2000.
[4] U. Knauer, Algebraic Graph Theory. Morphisms, monoids and matrices. De Gruyter,
Berlin and Boston 2011.
[5] P. Sirisathianwatthana, N. Pipattanajinda, Finding the number of cycle egamor-
phisms, Thai Journal of Mathematics, Special Issue (Annual Meeting in Mathematics,
2010), 1-9.
Contact information
U. Knauer Institut für Mathematik, Carl von Ossietzky
Universität, D-26111 Oldenburg, GERMANY
E-Mail(s): ulrich.knauer@uni-oldenburg.de
N. Pipattanajinda Program of Mathematics, Faculty of Sciences
and Technology, Kamphaeng Phet Rajabhat
University, Kamphaeng Phet, THAILAND
E-Mail(s): nirutt.p@gmail.com
Received by the editors: 24.11.2016
and in final form 09.12.2018.
|