问题描述：
英语翻译
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.
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.
问题解答：
我来补答展开全文阅读