Let $G\_i = (V\_i, E\_i)$ be simple, undirected graphs for $i=1,2$. A *graph homomorphism* is a map $f:V\_1\to V\_2$ such that $\{f(v), f(w)\}\in E\_2$ whenever $\{v,w\}\in E\_1$.


By $\text{Hom}(G\_1, G\_2)$ we denote the collection of graph homomorphisms from $G\_1$ to $G\_2$. Note that it is possible that $\text{Hom}(G\_1, G\_2)=\emptyset$.


[This paper](http://groupoids.org.uk/pdffiles/graphmorphisms-v15i1a1.pdf) is supposed to describe how we can make $\text{Hom}(G\_1, G\_2)$ into a graph - but I can't flesh out a criterion for: when do $f, g \in \text{Hom}(G\_1, G\_2)$ form an edge?



Exponential object in the category of simple, undirected graphs
The title of your question asks about "exponential object[s] in the category of simple, undirected graphs". I can tell you what they are.


(The body of your question asks about a construction in a specific paper, which I haven't read, so I can't answer *that* question directly. But of course, exponentials are unique when they exist.)


So: in the category of simple graphs that you mention, the exponentials $\mathrm{HOM}(G\_1, G\_2)$ are as follows. A vertex of $\mathrm{HOM}(G\_1, G\_2)$ is a function from the set of vertices of $G\_1$ to the set of vertices of $G\_2$. Two vertices $\phi, \psi$ of $\mathrm{HOM}(G\_1, G\_2)$ are adjacent iff whenever $x$ and $y$ are adjacent vertices of $G\_1$, then $\phi(x)$ and $\psi(y)$ are adjacent vertices of $G\_2$.


I'd recommend Godsil and Royle's book *Algebraic Graph Theory*. [This blog post](https://golem.ph.utexas.edu/category/2014/12/graph_colouring_and_cartesian.html) also says more about the cartesian closed category of simple graphs.


