Graph homomorphisms between trees

zbMATH Open1298.05062arXiv1307.6721MaRDI QIDQ463048FDOQ463048

Authors: Péter Csikvári, Zhicong Lin 

Publication date: 23 October 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this paper we study several problems concerning the number of homomorphisms of trees. We give an algorithm for the number of homomorphisms from a tree to any graph by the Transfer-matrix method. 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 of Bollob'as and Tyomkyn's result concerning the number of walks in trees. Some other highlights of the paper are the following. Denote by $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 $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$, ${\displaystyle }$exp(H_{lambda}(G))lambda^{m-1}leqhom(T_m,G),${\displaystyle }$ 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$. In the particular case when $G$ is the path $P_n$ on $n$ vertices, we prove that ${\displaystyle }$hom(P_m,P_n)leq hom(T_m,P_n)leq hom(S_m,P_n),${\displaystyle }$ where $T_m$ is any tree on $m$ vertices, and $P_m$ and $S_m$ denote the path and star on $m$ vertices, respectively. We also show that if $T_m$ is any fixed tree and ${\displaystyle }$hom(T_m,P_n)>hom(T_m,T_n),${\displaystyle }$ 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 ${\displaystyle }$ |End(P_m)|leq|End(T_m)|leq|End(S_m)|, ${\displaystyle }$ where $End(T_m)$ is the set of all endomorphisms of $T_m$ (homomorphisms from $T_m$ to itself).

Full work available at URL: https://arxiv.org/abs/1307.6721

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Homomorphisms of trees into a path
• Extremal graphs for homomorphisms
• A note on counting homomorphisms of paths
• On recognizing graphs by numbers of homomorphisms
• Asymptotic Enumeration of Spanning Trees

zbMATH Keywords

treesMarkov chainsadjacency matrixextremal problemsgraph homomorphismswalksKC-transformation

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

Cites Work

• Elements of Information Theory
• Title not available (Why is that?)
• Graph theory
• Title not available (Why is that?)
• On graphs with randomly deleted edges
• Walks and paths in trees
• Tree-minimal graphs are almost regular
• A partially ordered set of functionals corresponding to graphs
• Graph homomorphisms between trees
• Number of walks and degree powers in a graph
• A correlation inequality for bipartite graphs
• On a poset of trees
• An algorithm for the number of path homomorphisms
• On the number of congruence classes of paths
• On the eigenvalues of trees
• Multiplicities of subgraphs
• On a poset of trees. II
• Title not available (Why is that?)
• The homomorphism domination exponent

Cited In (11)

• On the distribution of range for tree-indexed random walks
• On local weak limit and subgraph counts for sparse random graphs
• Maximizing and minimizing the number of generalized colorings of trees
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• Extremal \(H\)-colorings of trees and 2-connected graphs
• Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree
• Homomorphisms of trees into a path
• Isomorphism Types of Trees
• Graph homomorphisms between trees
• Extremal graphs for Widom-Rowlinson colorings in \(k\)-chromatic graphs
• Sidorenko's conjecture, colorings and independent sets

This page was built for publication: Graph homomorphisms between trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463048)