Let me define undirected graphs - slightly deviating from common usage - not to be a symmetric binary relation on an *arbitrary finite* set, but on a *finite subset of* $\,\mathbb{N}$. Anyway I write $G = (V(G), E(G))$ where $V(G)\subset \mathbb{N}$ is the underlying set of vertices of the graph $G$ and $E(G)$ is its set of unordered pairs of vertices called edges.


There are - among others - two notions of morphisms for a category of undirected graphs: **[graph homomorphisms](http://en.wikipedia.org/wiki/Graph_homomorphism)** (the weaker notion, giving rise to the category $\mathcal{G}\_1$) and **[elementary embeddings](http://ncatlab.org/nlab/show/elementary+embedding)** (the stronger notion, giving rise to the category $\mathcal{G}\_2$, which is a subcategory of $\mathcal{G}\_1$).


For each **permutation** $\pi: \mathbb{N} \rightarrow \mathbb{N}$ there are (endo-)functors $F\_\pi$ both from $\mathcal{G}\_1$ to itself and from $\mathcal{G}\_2$ to itself which are definable in an obvious way:


$$V(F\_\pi(G)) = \pi(V(G))$$
$$\lbrace x,y\rbrace \in E(F\_\pi(G))\quad \text{iff}\quad \lbrace \pi^{-1}(x),\pi^{-1}(y) \rbrace \in E(G)$$
$$F\_\pi(f) = F\_{\pi} \circ f \circ F\_{\pi^{-1}}$$



> 
> *[Intermediate questions]*  
> 
>  1. Is it OK to write the definition of $F\_\pi(f)$ like this?  
> 
>  2. Can $F\_\pi$ - thus defined - be also a (somehow forgetful) functor from $\mathcal{G}\_2$ to $\mathcal{G}\_1$, but eventually not the other way around?
> 
> 
> 


Only for $\mathcal{G}\_2$ - i.e. for elementary embeddings as morphisms - there is (as I do believe) another "uniform" family of (endo-)functors from $\mathcal{G}\_2$ to itself. Consider formulas $\phi(x,y)$ of the first-order language with signature $\sigma = \lbrace E\,\rbrace$ with the binary relation symbol $E(x,y)$ indicating that $\lbrace x,y\rbrace \in E(G)$. For each such **formula** $\phi$ there is a "definition functor" $F\_\phi$ definable like this:


$$V(F\_\phi(G)) = V(G)$$
$$\lbrace x,y\rbrace \in E(F\_\phi(G))\quad \text{iff}\quad G \models \phi(x,y)$$
$$F\_\phi(f) = f$$


$f$ has to be seen as a map on the vertex set only, otherwise the functor condition $\operatorname{src}(F(f)) = F(\operatorname{src}(f))$ would not be fulfilled, because $F\_\phi(G)$ is another graph than $G$ (having the same vertex set only).



> 
> *[Intermediate question]* Are these "definition functors" $F\_\phi$ really functors?
> 
> 
> 


Assuming the latter, I have a bunch of questions (some more trivial than others, but I'd like to ask them all, because they belong together):



> 
> 1. Given a "permutation functor" $F\_\pi$: for which functors $F$ are there natural transformations $\eta$ from $F\_\pi$ to $F$ (and vice
>  versa)? Do these functors $F$ have to be permutation functors
>  themselves? If so: for which permutations $\pi'$ are there natural
>  transformations $\eta$ from $F\_\pi$ to $F\_{\pi'}$ (and vice versa)?
> 2. The same for "definition functors": Given a definition functor $F\_\phi$: for which functors $F$ are there natural transformations
>  $\eta$ from $F\_\phi$ to $F$ (and vice versa)? Do these functors $F$
>  have to be definition functors themselves? If so: for which
>  formulas $\phi'$ are there natural transformations $\eta$ from
>  $F\_\phi$ to $F\_{\phi'}$ (and vice versa)?
> 3. What are examples of endo-functors of $\mathcal{G}\_2$ that are not finite combinations of permutation and definition functors?
> 
> 
> 



Endofunctors of graph categories
I have to think about this a bit.


Some first remarks: Why do you need to consider propper subsets? From a category theoretic view it is easier to work with the comma-category
$$\mathrm{FinGrph}/\mathsf{blob}(\mathbb N)$$
a.k.a. finite graphs together with a graph morphism $s:G\to \mathsf{blob}(\mathbb N):=(\mathbb N,\mathbb N\times \mathbb N)$ a.k.a. finite graphs $G$ together with a map $s:V(G)\to\mathbb N$. This category is not equivalent to your $\mathcal G\_1$ but contains it as a full reflective subcategory:


Given a Graph $G$ and a map $s:V(G)\to X$ you can push forward the graph structure on $V(G)$ to a graph structure $s\_\*G$ on $X$ by defining
$$(x,x')\in E(s\_\*G):\Leftrightarrow \exists(v,v')\in E(G):sv=x,sv'=x'.$$
Now do this for the maps $\overline{s}:V(G)\to\mathrm{im}(s)\subset \mathbb N$. This defines a functor $\mathrm{FinGrph}/\mathsf{blob}(\mathbb N)\to \mathcal G\_1$ left-adjoint to the obvious inclusion functor. (This is due to $s\_\*G$ being the *final* graph structure on $X$ for the map $s$.)


The permutation functor $F\_\pi$ then appears by postcomposition with $\pi$ by mapping $s:G\to\mathsf{blob}(\mathbb N)$ to $\mathsf{blob}(\pi)\circ s$.


