On recognizing graphs by numbers of homomorphisms
Zdenĕk Dvořák · Journal of Graph Theory · 2009
Abstract Let hom (G, H) be the number of homomorphisms from a graph G to a graph H. A well‐known result of Lovász states that the function hom (·, H) from all graphs uniquely determines the graph H up to isomorphism. We study this function restricted to smaller classes of graphs. We show that several natural classes (2‐degenerate graphs and graphs homomorphic to an arbitrary non‐bipartite graph) are sufficient to recognize all graphs, and provide a description of graph properties that are recognizable by graphs with bounded tree‐width. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 330–342, 2010