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](http://dx.doi.org/10.1007/BF02280291) ([reprint](http://www.cs.elte.hu/~lovasz/scans/opstruct.pdf))


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](http://dx.doi.org/10.1006/jctb.2000.1988)


There are at least two related MO questions: [*Complete graph invariants?*](https://mathoverflow.net/questions/11631/complete-graph-invariants) and [*Invariants that might determine a graph up to isomorphism*](https://mathoverflow.net/questions/52141/invariants-that-might-determine-graph-up-to-isomorphism) although these address a somewhat different question.



Do right-profiles determine graphs up to isomorphism?
It is true. It's Exercise 11 on page 128 of "Algebraic Graph Theory", by Royle and somebody.
If I recall correctly (and I might not) the trick is to show that the number of homomorphisms determines the number of injective homomorphisms. [EDIT: as Andras notes, I should have said surjections.]


The result is quite old, and I am somewhat surprised that it's not in the paper of Lovász
you cite.


