Papers
Homomorphisms of trees into a path
- AuthorZhicong Lin
- JournalSIAM Journal on Discrete Mathematics 29 (2015
- Link https://doi.org/10.1137/140993995
- Classification of papersSCI
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