# Do right-profiles determine graphs up to isomorphism?

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.

• Just so I get clear: we are talking graphs as digraphs with loops? and homomorphisms are certain maps of vertex sets? So that h(G,H)=1 and h(H,G)=0, with G being a graph having only one edge between its two vertices and H has only one loop on one of its two vertices? I can imagine the answer being different if homomorphisms were (based on) edge maps. Gerhard "Mucking With The Details Again" Paseman, 2013.06.04 – Gerhard Paseman Jun 4 '13 at 21:07
• There is also the issue of (v,u) in G COND (h(u),h(v)) in H, where COND could be either implies or iff, depending on how you like your graph map h from G to H. Gerhard "Rusty In Dealing With Relationships" Paseman, 2013.06.04 – Gerhard Paseman Jun 4 '13 at 21:14
• Usual notion of homomorphism, as in the Lovász paper: $u~v$ implies $f(u)~f(v)$. People don't seem to worry about loops and multi-edges in this context because it often seems easy to translate between the graph/multigraph cases with small tweaks. – András Salamon Jun 5 '13 at 0:16