On recognizing graphs by numbers of homomorphisms

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

Published by

Original source : http://dx.doi.org/10.1002%2Fjgt.20461...