英语翻译
ON THE NUMBER OF CONGRUENCE CLASSES OF PATHS
ZHICONG LIN AND JIANG ZENG
Abstract.Let Pn denote the undirected path of length n − 1.The cardinality of the set of congruence classes induced by the graph homomorphisms from Pn onto Pk is determined.This settles an open problem of Michels and Knauer (Disc.Math.,309 (2009) 5352-5359).Our result is based on a new proven formula of the number of homomorphisms between paths.
Keywords:Graph,graph endomorphisms,graph homomorphisms,paths,lattice paths
1.Introduction
We use standard notations and terminology of graph theory in [3] or [6,Appendix].The graphs considered here are finite and undirected without multiple edges and loops.Given a graph G,we write V (G) for the vertex set and E(G) for the edge set.A homomorphism from a graph G to a graph H is a mapping f :V (G) → V (H) such that the images of adjacent vertices are adjacent.An endomorphism of a graph is a homomorphism from the graph to itself.Denote by Hom(G,H) the set of homomorphisms from G to H and by End(G) the set of endomorphisms of a graph G.For any finite set X we denote by |X| the cardinality of X.A path with n vertices is a graph whose vertices can be labeled v1,...,vn so that vi and vj are adjacent if and only if |i − j| = 1; let Pn denote such a graph with vi = i for 1 ≤ i ≤ n.Every endomorphism f on G induces a partition ρ of V (G),also called the congruence classes induced by f,with vertices in the same block if they have the same image.
Let C (Pn) denote the set of endomorphism-induced partitions of V (Pn),and let |ρ| denote the number of blocks in a partition ρ.For example,if f ∈ End(P4) is defined by f(1) = 3,f(2) = 2,f(3) = 1,f(4) = 2,then the induced partition ρ is {{1},{2,4},{3}} and |ρ| = 3.
The problem of counting the homomorphisms from G to H is difficult in general.How- ever,some algorithms and formulas for computing the number of homomorphisms of paths have been published recently (see [1,2,5]).In particular,Michels and Knauer [5] give an algorithm based on the epispectrum Epi(Pn) of a path Pn.They define Epi(Pn) = (l1(n),...,ln−1(n)),where
lk(n) = |{ρ ∈ C (Pn) :|ρ| = n − k + 1}|.(1.1)
Here a misprint in the definition of lk(n) in [5] is corrected.
In [5],based on the first values of lk(n),Michels and Knauer speculated the following conjecture.