Graph homomorphisms between trees (Q463048)

Summary: In this paper we study several problems concerning the number of~homomorphisms of trees. We begin with an algorithm for the number of homomorphisms~from a tree to any graph. By using this~algorithm and some transformations on trees, we study various extremal problems about the number of homomorphisms of trees. These applications include a far reaching generalization and a dual of Bollobás and Tyomkyn's result concerning the number of walks in trees.{ }Some other main results of the paper are the following. Denote by \(\mathrm{hom}(H,G)\) the number of homomorphisms from a graph \(H\) to a graph \(G\). For any tree \(T_m\) on \(m\) vertices we give a general lower bound for \(\mathrm{hom}(T_m,G)\) by certain entropies of Markov chains defined on the graph \(G\). As a particular case, we show that for any graph \(G\), \[ \exp(H_\lambda(G))\lambda^{m-1}\leqslant\mathrm{hom}(T_m,G), \] where \(\lambda\) is the largest eigenvalue of the adjacency matrix of \(G\) and \(H_\lambda(G)\) is a certain constant depending only on \(G\) which we call the~spectral entropy of \(G\). We also show that if \(T_m\) is any fixed tree and \[ \mathrm{hom}(T_m,P_n)>\mathrm{hom}(T_m,T_n), \] for some tree \(T_n\) on \(n\) vertices, then \(T_n\) must be the tree obtained from a path \(P_{n-1}\) by attaching a pendant vertex to the second vertex of \(P_{n-1}\).{ }All the results together enable us to show that among all trees with fixed number of vertices, the path graph has the fewest number of endomorphisms while the star graph has the most.