For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$. Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, which contains only one representative from each isomorphism class. The right $\mathbf{D}$-profile of a graph $G$ is the infinite vector $(G \to \mathbf{D}) := (h(G,G_1),h(G,G_2),\dots)$.
Is it true that $(G\to \mathbf{D}) = (H\to \mathbf{D})$ iff $G \simeq H$?
The analogous left-profile is important in the theory of graph limits. Lovász showed that $(\mathbf{D}\to G) = (\mathbf{D}\to H)$ iff $G \simeq H$.
- L. Lovász, Operations with structures, Acta Mathematica Hungarica 18(3), 1967, 321–328. doi:10.1007/BF02280291 (reprint)
It is also possible to restrict $\mathbf{D}$ to be a smaller set, for instance just the complete graphs. In this case, right-profile equivalence implies that $G$ and $H$ have the same chromatic polynomials. A conjecture of Bollobás, Pebody and Riordan about the chromatic polynomial implies that this is enough to show isomorphism for almost all graphs, although they also showed that it is likely to be nontrivial to construct examples of non-isomorphic graphs $G$ and $H$ which have the same right-profiles with respect to the set of complete graphs.
One can also ask whether there is a set of target graphs (strictly smaller than the set $\mathbf{D}$ of all graphs) that can be used to determine graph isomorphism; clearly this would imply my question. If such a set is well-known, then I would appreciate a hint or pointer.
- B. Bollobás, L. Pebody, O. Riordan, Contraction-deletion invariants for graphs, JCTB 80, 2000, 320–345. doi:10.1006/jctb.2000.1988
There are at least two related MO questions: Complete graph invariants? and Invariants that might determine a graph up to isomorphism although these address a somewhat different question.
