Suppose $G$ is a group and $S \subset G$ is its finite subset. Let’s define the commuting graph of $G$ in respect to $S$ as $Comm(G, S)$ - a graph, where the vertices are the elements of $S$, and they are connected with edges iff they commute.
Let’s define the commuting graph representation number as the minimal number $CGRN(n)$, such that any $n$-vertex graph is isomorphic to a commuting subgraph of some group of order $CGRN(n)$.
My question is:
Is there some exact formula (or at least asymptotic) for $CGRN(n)$?
The only thing that I managed to prove, were the following bounds (which is quite a weak result, as the lower bound is linear, but the upper bound is exponential):
$$\frac{8(n-1)}{5} \leq CGRN(n) \leq 4^n$$
The proof of the lower bound:
According to Erdos-Turan-Gustafson theorem any commuting graph on a non-abelian group $G$ has clique number not exceeding $\frac{5}{8}G$. And it is quite obvious, that if $G$ is abelian, then all its commuting graphs are complete. So, if we have a graph with $n$ vertices and the clique number $n-1$ (to get such graph, you may remove any single edge from $K_n$), then the minimal group, such that this graph is a commuting graph in $G$ must have order at last $\frac{8(n-1)}{5}$.
The proof of the upper bound:
For any $n$ vertex graph $\Gamma(V, E)$, where $V = \{1, 2, … n\}$ such group and the corresponding subset can be explicitly constructed as
$$G = \langle \{a_v\}_{v \in V} | \{a_v^4 = e\}_{v \in V}, \{a_ua_v = a_va_u\}_{(v, u) \in E}, \{a_ua_va_u = a_v\}_{(u, v)\notin E, u \leq v} \rangle$$ $$S = \{a_v\}_{v \in V}$$
Here's how to prove an improved upper bound of $2^{n+1}$.
Take the same graph on $n$ vertices as in your example, and consider the following group:
$G=\left\langle a_1,\ldots,a_n,z| a_i^2=z^2=[a_i,z]=1\quad \forall i, [a_i,a_j]=\begin{cases} 1 \quad\textrm{if \{i,j\} is an edge} \\ z \quad\textrm{otherwise}\end{cases}\right\rangle$.
I believe this group has order $2^{n+1}$ and taking $S=\{a_1,\ldots,a_n\}$ will give the desired graph.
Using a computer, I checked that for $C_4\cong K_{2,2}$, the smallest group indeed has order $32$ (and arises essentially in this way), so this bound is tight for $n=4$.
EDIT: Combined with the answer at Minimal possible order of a group that contains a specific subset this shows that $2^{n+1}$ is the correct bound (at least for $n$ even).