【英语翻译ONTHENUMBEROFCONGRUENCECLASSESOFPATHSZHICONGLINANDJIANGZENGAbstract.LetPndenotetheundirectedpathoflengthn−1.ThecardinalityofthesetofcongruenceclassesinducedbythegraphhomomorphismsfromPnontoPkis】

　　英语翻译

　　ONTHENUMBEROFCONGRUENCECLASSESOFPATHS

　　ZHICONGLINANDJIANGZENG

　　Abstract.LetPndenotetheundirectedpathoflengthn−1.ThecardinalityofthesetofcongruenceclassesinducedbythegraphhomomorphismsfromPnontoPkisdetermined.ThissettlesanopenproblemofMichelsandKnauer(Disc.Math.,309(2009)5352-5359).Ourresultisbasedonanewprovenformulaofthenumberofhomomorphismsbetweenpaths.

　　Keywords:Graph,graphendomorphisms,graphhomomorphisms,paths,latticepaths

　　1.Introduction

　　Weusestandardnotationsandterminologyofgraphtheoryin[3]or[6,Appendix].Thegraphsconsideredherearefiniteandundirectedwithoutmultipleedgesandloops.GivenagraphG,wewriteV(G)forthevertexsetandE(G)fortheedgeset.AhomomorphismfromagraphGtoagraphHisamappingf:V(G)→V(H)suchthattheimagesofadjacentverticesareadjacent.Anendomorphismofagraphisahomomorphismfromthegraphtoitself.DenotebyHom(G,H)thesetofhomomorphismsfromGtoHandbyEnd(G)thesetofendomorphismsofagraphG.ForanyfinitesetXwedenoteby|X|thecardinalityofX.Apathwithnverticesisagraphwhoseverticescanbelabeledv1,...,vnsothatviandvjareadjacentifandonlyif|i−j|=1;letPndenotesuchagraphwithvi=ifor1≤i≤n.EveryendomorphismfonGinducesapartitionρofV(G),alsocalledthecongruenceclassesinducedbyf,withverticesinthesameblockiftheyhavethesameimage.

　　LetC(Pn)denotethesetofendomorphism-inducedpartitionsofV(Pn),andlet|ρ|denotethenumberofblocksinapartitionρ.Forexample,iff∈End(P4)isdefinedbyf(1)=3,f(2)=2,f(3)=1,f(4)=2,thentheinducedpartitionρis{{1},{2,4},{3}}and|ρ|=3.

　　TheproblemofcountingthehomomorphismsfromGtoHisdifficultingeneral.How-ever,somealgorithmsandformulasforcomputingthenumberofhomomorphismsofpathshavebeenpublishedrecently(see[1,2,5]).Inparticular,MichelsandKnauer[5]giveanalgorithmbasedontheepispectrumEpi(Pn)ofapathPn.TheydefineEpi(Pn)=(l1(n),...,ln−1(n)),where

　　lk(n)=|{ρ∈C(Pn):|ρ|=n−k+1}|.(1.1)

　　Hereamisprintinthedefinitionoflk(n)in[5]iscorrected.

　　In