# Finding the Number of Weak Homomorphisms of Paths

Authors: Tawatchai Pomsri; Wannasiri Wannasit; Sayan Panma
Journal: Journal of Mathematics
 (2022)

---

## Abstract

LetG and H be graphs. A mapping f from VG to VH is called a weak homomorphism from G to H if fx=fy or fx,fy∈EH whenever x,y∈EG. In this paper, we provide an algorithm to determine the number of weak homomorphisms of paths.


---

## Body

## 1. Introduction

LetG and H be graphs. A mapping f:VG⟶VH is a homomorphism from G to H if f preserves the edges, i.e., if fx,fy∈EH whenever x,y∈EG. A homomorphism from G to G itself is called an endomorphism on G. Denote the set of homomorphisms from G to H by Hom(G,H) and the set of endomorphisms on G by End(G). Clearly, End(G) forms a monoid under composition of mappings. Let Pn denote a path of order n such that VPn=0,1,⋯,n−1 and EPn=i,i+1i=0,1,⋯,n−2. Let Cn denote a cycle of order nn≽3 such that VCn=0,1,⋯,n−1 and ECn=i,i+1i=0,1,⋯,n−1, where + is the addition modulo n. Furthermore, we will refer to [1, 2] for more information about graphs and algebraic graphs.There are many interesting results concerning graphs and their homomorphisms (or endomorphism monoids). In 1992, Böttcher and Knauer [3] gave an account of the different ways to define homomorphisms of graphs, which leads to six classes of endomorphisms for each graph, i.e., endomorphisms, half-strong endomorphisms, locally-strong endomorphisms, quasi-strong endomorphisms, strong endomorphisms, and automorpisms. The formulas for the number of graph homomorphisms and the number of graph endomorphisms are the important tools for studying the structures of Hom(G,H) and End(G), respectively. The formula for the number of endomorphisms on paths End(Pn) was introduced by Arworn [4] in 2009. She gave the formula in terms of the numbers of shortest paths from the point 0,0 to any point i,j in an r-ladder square lattice. Furthermore, in the same year, Arworn and Wojtylak [5] gave the formula for the number of homomorphisms of paths Hom(Pm,Pn) in terms of the order of Homji(Pm,Pn) where HomjiPm,Pn=f∈HomPm,Pn∣f0=i,fm−1=j for all i,j∈0,1,⋯,n−1.For a mappingf:VG⟶VH, we say that f contracts an edge x,y if fx=fy. The point is that homomorphisms have to preserve edges. If we have the possibility of contracting edges as well, then this could also be achieved with usual homomorphisms when our graphs contain a loop at every vertex.A mappingf:VG⟶VH is called a weak homomorphism from a graph G to a graph H (also called an egamorphism) if f contracts or preserves the edges, i.e., if fx=fy or fx,fy∈EH whenever x,y∈EG. A weak homomorphism from G to G itself is called a weak endomorphism on G. Denote the set of weak homomorphisms from G to H by WHom(G,H), and the set of weak endomorphisms on G by WEnd(G). Clearly, WEnd(G) forms a monoid under composition of mappings.In 2010, Sirisathianwatthana and Pipattanajinda [6] gave the number of weak homomorphisms of cycles WHomCm,Cn in terms of the order of WHomjiPm−1,Cn where WHomjiPm−1,Cn=f∈WHomPm−1,Cn∣f0=i,fm−1=j for all i,j∈0,1,⋯,n−1. Recently, in 2018, Knauer and Pipattanajinda [7] introduced the number of weak endomorphisms on paths WEnd(Pn) in terms of the numbers 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. In this paper, we are interested in finding the number of weak homomorphisms of paths WHom(Pm,Pn) in terms of Am−1,ni, Bm−1,ni, and Cm−1,ni where Am−1,ni=f∈WHomPm−1,Pn∣f0=i, Bm−1,ni=f∈WHomPm−1,Pn∣f0=iandfm−2=0, Cm−1,ni=f∈WHomPm−1,Pn∣f0=iandfm−2=n−1 for all i∈0,1,⋯,n−1.


## 2. The Number of Weak Homomorphisms of Paths

In this section, we give the number of weak homomorphisms fromPm to Pn,i.e.,WHomPm,Pn. We see at once that WHomP1,Pn=n and WHomPm,P1=1. The task is now to find WHomPm,Pn for all m,n∈ℕ−1. For i∈0,1,⋯,n−1, let Am,ni=f∈WHomPm,Pn∣f0=i, Bm,ni=f∈WHomPm,Pn∣f0=iandfm−1=0, Cm,ni=f∈WHomPm,Pn∣f0=iandfm−1=n−1, and Dm,ni=f∈WHomPm,Pn∣f0=iandfm−1≠0andfm−1≠n−1. It is clear that Am,ni∣i=0,1,⋯,n−1 is a partition of WHom(Pm, Pn), and Bm,ni,Cm,ni,Dm,ni is a partition of Am,ni. By the definition of a weak homomorphism, if f0=i then i−j≤fj≤i+j for all i∈0,1,⋯,n−1 and j∈0,1,⋯,m−1. It follows that if f0≥m, then 1≤fm−1. This gives Bm,ni=∅ for all i≥m. Similary, if f0≤m−2, then fm−1≤2m−3<n−1. We thus get Cm,ni=∅ for all i≤m−2. For simplicity of notation, we some time write f=f0f1⋯fm−1 instead of f=01⋯m−1f0f1⋯fm−1.Example 1.
Consider the weak homomorphisms fromP3 to P6. We see that WHomP3,P6=A3,60∪A3,61∪A3,62∪A3,63∪A3,64∪A3,65 where A3,60=000,001,010,011,012, A3,61=100,101,110,111,112,121,122,123, A3,62=210,211,212,221,222,223,232,233,234, A3,63=321,322,323,332,333,334,343,344,345, A3,64=432,433,434,443,444,445,454,455, and A3,65=543,544,545,554,555. Moreover, we get A3,6i=B3,6i∪C3,6i∪D3,6i for all i=0,1,⋯,5 where
(1)B3,60=000,010,C3,60=∅,D3,60=001,011,012,B3,61=100,110,C3,61=∅,D3,61=101,111,112,121,122,123,B3,62=210,C3,62=∅,D3,62=211,212,221,222,223,232,233,234,B3,63=∅,C3,63=345,D3,63=321,322,323,332,333,334,343,344,B3,64=∅,C3,64=445,455,D3,64=432,433,434,443,444,454,B3,65=∅,C3,65=545,555,D3,65=543,544,554.
Let us look at the order of the setsA3,6i, B3,6i, and C3,6i in Example 1, we see that A3,60=A3,65, A3,61=A3,64, A3,62=A3,63, and B3,6i=C3,66−i+1 for all i=0,1,2. In the first two lemmas, we consider about some relations of the order of Am,ni, Bm,ni, and Cm,ni for all i=0,1,⋯,n−1.Lemma 2.
Letm,n∈ℕ−1. Then Am,ni=Am,nn−i+1 for all i=0,1,⋯,n−1.
Proof. Let i∈0,1,⋯,n−1 and f∈Am,ni. Define g:VPm⟶VPn by gj=fj+n−2fj+1 for all j∈0,1,⋯,m−1. We first prove that g is a weak homomorphism. Let x,y∈EPm. To show that gx=gy or gx,gy∈EPn. Since x,y∈EPm and f is a weak homomorphism, we get fx=fy or fx,fy∈EPn.Case 1.
Iffx=fy, then
(2)gx=fx+n−2fx+1=fy+n−2fy+1=gy.Case 2.
Iffx,fy∈EPn, then fx=fy+1 or fx=fy−1.Case 2.1.
Iffx=fy+1, then
(3)gx=fx+n−2fx+1=fy+1+n−2fy+1+1=fy+n−2fy+1−1=gy−1.
It follows thatgx,gy∈EPn.Case 2.2.
Iffx=fy−1, then
(4)gx=fx+n−2fx+1=fy−1+n−2fy−1+1=fy+n−2fy+1+1=gy+1.This givesgx,gy∈EPn.From Case1 and Case 2, we conclude that g∈ WHomPm,Pn. Since g0=f0+n−2f0+1=i+n−2i+1=n−i+1, we get g∈Am,nn−i+1. Define ϕ:Am,ni⟶Am,nn−i+1 by ϕf=f+n−2f+1 for all f∈Am,ni. We will show that ϕ is bijective. Let f1,f2∈Am,ni such that ϕf1=ϕf2. Therefore, for all x∈VPm,
(5)ϕf1x=ϕf2x,f1x+n−2f1x+1=f2x+n−2f2x+1,f1x=f2x.The result isf1=f2. So ϕ is injective. Let g∈Am,nn−i+1. Define f:VPm⟶VPn by fj=−gj+n−1. In the same manner as proved above, we get f∈ WHomPm,Pn. Since f0=i, we have f∈Am,ni for all j∈0,1,⋯,m−1. As ϕf=g, we get ϕ is surjective. Hence ϕ is bijective and so Am,ni=Am,nn−i+1 for all i=0,1,⋯,n−1.Lemma 3.
Letm,n∈ℕ−1.
(1)
Bm,ni=Cm,nn−i+1 for all i=0,1,⋯,n−1.(2)
Ifn>2m−2, then Am,nj=Am,nk for all j,k∈m−1,m,⋯,n−m.
Proof. 1. Consider the function ϕ in the proof of Lemma 2. It is easy to check that ϕBm,ni=Cm,nn−i+1. This gives Bm,ni=Cm,nn−i+1 for all i=0,1,⋯,n−1.
2. Letn>2m−2. Then m−1,m,⋯,n−m≥1. Define ϕ: Am,nj⟶Am,nk by ϕf=f+k−j for all f∈Am,nj. By similar arguments as in Lemma 2, we also conclude that ϕ is bijective.The following lemma gives the order ofAm,ni in terms of Am−1,ni, Bm−1,ni and Cm−1,ni.Lemma 4.
Letm,n∈ℕ−1. Then Am,ni=3Am−1,ni−Bm−1,ni−Cm−1,ni for all i∈0,1,⋯,n−1.
Proof. Let f∈Am−1,ni and f′:VPm⟶VPn such that f′0,1,⋯,m−2=f.
Sincef∈Bm−1,ni⟷f′∈g1,g2⊆Am,ni⟷f′∈Am,ni and f′m−2=0 where
(6)g1x=fxifx=0,1,⋯,m−20ifx=m−1,g2x=fxifx=0,1,⋯,m−21ifx=m−1,then in this case we obtain 2Bm−1,ni weak homomorphisms in Am,ni.
Sincef∈Cm−1,ni⟷f′∈t1,t2⊆Am,ni⟷f′∈Am,ni and f′m−2=n−1, where
(7)t1x=fxifx=0,1,⋯,m−2n−1ifx=m−1,t2x=fxifx=0,1,⋯,m−2n−2ifx=m−1,then in this case we get 2Cm−1,ni weak homomorphisms in Am,ni.
Sincef∈Dm−1,ni⟷f′∈h1,h2,h3⊆Am,ni⟷f′∈Am,ni and f′m−2∉0,n−1, where
(8)h1x=fxifx=0,1,⋯,m−2fm−2ifx=m−1,h2x=fxifx=0,1,⋯,m−2fm−2+1ifx=m−1,h3x=fxifx=0,1,⋯,m−2fm−2−1ifx=m−1,then in this case we have 3Dm−1,ni weak homomorphisms in Am,ni.
Thus, we conclude thatAm,ni=3Dm−1,ni+2Bm−1,ni+2Cm−1,ni=3Dm−1,ni+3Bm−1,ni−Bm−1,ni+3Cm−1,ni−Cm−1,ni=3Dm−1,ni+Bm−1,ni+Cm−1,ni−Bm−1,ni−Cm−1,ni. Since Am−1,ni=Dm−1,ni+Bm−1,ni+Cm−1,ni, it follows that Am,ni=3Am−1,ni−Bm−1,ni−Cm−1,ni.Example 5.
Consider the weak homomorphisms fromP2 to P6. We have WHomP2,P6=A2,60∪A2,61∪A2,62∪A2,63∪A2,64∪A2,65 where
(9)A2,60=00,01,B2,60=00,C2,60=∅,D2,60=01,A2,61=10,11,12,B2,61=10,C2,61=∅,D2,61=11,12,A2,62=21,22,23,B2,62=∅,C2,62=∅,D2,62=21,22,23,A2,63=32,33,34,B2,63=∅,C2,63=∅,D2,63=32,33,34,A2,64=43,44,45,B2,64=∅,C2,64=45,D2,64=43,44,A2,65=54,55,B2,65=∅,C2,65=55,D2,65=54.
Consider the setsA3,6i in Example 1, we see that A3,6i=3A2,6i−B2,6i−C2,6i.
The next theorem gives the order of WHomPm,Pn in terms of Am−1,ni, Bm−1,ni and Cm−1,ni for all i=0,1,⋯,m−1.Theorem 6.
Letm,n∈ℕ−1.
(1)
Ifn is even, then WHomPm,Pn=23Am−1,n0−Bm−1,n0−Cm−1,n0+23Am−1,n1−Bm−1,n1−Cm−1,n1+⋯+23Am−1,nn/2−1−Bm−1,nn/2−1−Cm−1,nn/2−1.(2)
Ifn is odd, then WHomPm,Pn=23Am−1,n0−Bm−1,n0−Cm−1,n0+23Am−1,n1−Bm−1,n1−Cm−1,n1+⋯+23Am−1,nn/2−1−Bm−1,nn/2−1−Cm−1,nn/2−1+3Am−1,nn/2−Bm−1,nn/2−Cm−1,nn/2.
Proof. Since WHomPm,Pn=Am,n0+Am,n1+⋯+Am,nn−1, by Lemma 2, we have
(10)WHomPm,Pn=2Am,n0+2Am,n1+⋯+2Am,nn/2−1ifniseven,2Am,n0+2Am,n1+⋯+2Am,nn2−1+Am,nn/2ifnisodd.
By Lemma4, we get the statements 1 and 2.Theorem 7.
Letm,n∈ℕ−1. If n>2m−2, then WHomPm,Pn=23Am−1,n0−Bm−1,n0+23Am−1,n1−Bm−1,n1+⋯+23Am−1,nm−2−Bm−1,nm−2+n−2m+23Am−1,nm−1−Bm−1,nm−1.
Proof. Suppose that n>2m−2. Then m−1,m,⋯,n−m=n−2m+2. Since WHomPm,Pn=Am,n0+Am,n1+⋯+Am,nn−1, by Lemma 2 and Lemma 3 (2), we have WHomPm,Pn=2Am,n0+2Am,n1+⋯+2Am,nm−2+n−2m+2Am,nm−1. Consider Cm−1,ni=f∈WHomPm−1,Pn∣f0=iandfm−2=n−1. We see that if f0=i then fm−2≤i+m−2. It follows that if f0≤m−1 then fm−2≤2m−3<n−1. Thus Cm−1,ni=∅ for all i=0,1,⋯,m−1. So, by Lemma 4, Am,ni=3Am−1,ni−Bm−1,ni for all i=0,1,⋯,m−1. It follows that WHomPm,Pn=23Am−1,n0−Bm−1,n0+23Am−1,n1−Bm−1,n1+⋯+23Am−1,nm−2−Bm−1,nm−2+n−2m+23Am−1,nm−1−Bm−1,nm−1.Example 8.
From Example1, we have WHomP3,P6=44. Consider WHomP2,P6 in Example 5 we see that
(11)WHomP3,P6=23A2,60−B2,60+23A2,61−B2,61+23A2,62−B2,62=232−1+232−1+232−0=10+16+18=44.
In the following lemmas, we give the order ofAm,nm−1 and Am,nm−2.Lemma 9.
Letm,n∈ℕ−1. If n>2m−2, then Am,nm−1=3Am−1,nm−1−Bm−1,nm−1=3m−1 for all m∈ℕ.
Proof. Let f∈Am−1,nm−1. Then f0=m−1, and so 1=m−1−m−2≤fm−2≤m−1+m−2=2m−3. So, for each i∈0,1,⋯,m−3, if fi=k then there are 3 possible choises for fi+1 which are k−1,k, and k+1. By the multiplication principle, Am−1,nm−1=3m−2. Since Bm−1,nm−1=∅ and Cm−1,nm−1=∅, we have Am,nm−1=33m−2=3m−1 by Lemma 4.Lemma 10.
Letm,n∈ℕ−1. If n>2m−2, then Am,nm−2=3Am−1,nm−2−Bm−1,nm−2=3m−1−1 for all m∈ℕ.
Proof. Let f∈Am−1,nm−2. Then f0=m−2, and 1=m−2−m−3≤fm−3≤m−2+m−3=2m−5. So, for each i∈0,1,⋯,m−3, if fi=k then there are 3 possible choices for fi+1 which are k−1,k, and k+1. By the multiplication principle, Am−1,nm−2=3m−2. It easy to see that f∈Bm−1,nm−2↔f0=m−2 and fm−2=0↔f=m−2m−3⋯10. Thus Bm−1,nm−2=1. Since Cm−1,nm−2=∅, we get Am,nm−2=33m−2−1=3m−1−1 by Lemma 4.In light of Theorem7, Lemma 9, and Lemma 10, we have the following.Corollary 11.
Letm,n∈ℕ−1. If n>2m−2, then WHomPm,Pn=23Am−1,n0−Bm−1,n0+23Am−1,n1−Bm−1,n1+⋯+23Am−1,nm−3−Bm−1,nm−3+23m−1−1+n−2m+23m−1.



---

*Source: 2153927-2022-10-03.xml*