논문
Homomorphisms of trees into a path
- 저자Zhicong Lin
- 학술지SIAM Journal on Discrete Mathematics 29
- 등재유형
- 게재일자(2015)
Let ${{hom}}(G,H)$ denote the number of homomorphisms from a graph $G$ to a graph $H$. In this paper we study the number of homomorphisms of trees into a path, and prove that ${{hom}}(P_m,P_n)\leq {{hom}}(T_m,P_n)\leq {{hom}}(S_m,P_n),$ where $T_m$ is any tree on $m$ vertices, and $P_m$ and $S_m$ denote the path and star on $m$ vertices, respectively. This completes the study of extremal problems concerning the number of homomorphisms between trees started in the paper Graph Homomorphisms Between Trees
Let ${{hom}}(G,H)$ denote the number of homomorphisms from a graph $G$ to a graph $H$. In this paper we study the number of homomorphisms of trees into a path, and prove that ${{hom}}(P_m,P_n)\leq {{hom}}(T_m,P_n)\leq {{hom}}(S_m,P_n),$ where $T_m$ is any tree on $m$ vertices, and $P_m$ and $S_m$ denote the path and star on $m$ vertices, respectively. This completes the study of extremal problems concerning the number of homomorphisms between trees started in the paper Graph Homomorphisms Between Trees
