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 also says more about the cartesian closed category of simple graphs.