A question on "generating graphs"

Question

Suppose $H$ is a group. $X \subset H$, $|X| < \infty$. Let’s define $GG(H, X)$ (generating graph of $H$) as a finite undirected simple graph $\Gamma(V, E)$, such that $V = X$, $E = \{(x, y) \in X \times X| x \neq y, \langle x, y \rangle = H\}$.

$GG(H, X)$ has following properties (which are relatively obvious):

If $K < H$, then $GG(K, K \cap X)$ is a subgraph of the complementary graph of $GG(H, X)$

If $\phi: H \to K$ is a surjective group homomorphism, such that $\phi|_X$ is injective. then $GG(K, \phi(X))$ contains $GG(H, \phi(X))$ as a subgraph.

$Stab(X, Aut(H)) \leq Aut(GG(H, X))$, where $Stab(X, Aut(H)) = \{\phi \in Aut(H)| \phi(X) = X\}$

My question however is:

Does for any finite simple undirected graph $\Gamma$, there exist such a group $H$ and its finite subset $X$, that $\Gamma \cong GG(H, X)$?

I failed to construct such $H$ and $X$ for arbitrary $\Gamma$, however a counterexample does not come to my mind either.

Answer 1

For any finite simple undirected graph $\Gamma$, does there exist a group $H$ and a finite subset $X$, such that $\Gamma \cong GG(H, X)$?

Yes, and in fact, we can do it only with the group of integers under addition, $\mathbb{Z}$, using two basic number theoretic properties:

1. Two integers $n$ and $m$ in $\mathbb{Z}$ generate all of $\mathbb{Z}$ if and only if they are relatively prime.

2. There are infinitely many prime numbers.

Suppose the graph $\Gamma$ is given, and consider its complement graph, $\Gamma^c$, i.e., the graph with the same vertex set as $\Gamma$ and with two vertices connected by an edge in $\Gamma^c$ if and only if they are not connected by an edge in $\Gamma$.

Now, we assign a distinct positive prime integer to every vertex and every edge in $\Gamma^c$. We can do this because the graph is finite but the primes are infinite. Next, we define a vertex labeling as follows: we label vertex $v$ with the product of all the prime numbers on edges adjacent to $v$ as well as the prime number assigned to $v$. (Technically, we don't need to assign prime numbers originally to the vertices, but this ensures the added condition that no element in $X$ will generate $\mathbb{Z}$ on its own, which seems to be in the spirit of your original question.)

Next, we let $X = \{ n \in \mathbb{Z} \mid n\textrm{ is the label of a vertex } v \in \Gamma^c\}$. (Don't mix up the primes initially assigned to the vertices with their final labels which are products of primes.)

Now, let's build $GG(\mathbb{Z}, X)$. Since $|X| = |V(\Gamma)|$, $GG(\mathbb{Z}, X)$ has the same vertex set as $\Gamma$. Two numbers $n$ and $m$ in $X$ generate all of $\mathbb{Z}$ exactly when they are relatively prime, which since we used all distinct primes in our assignment, happens exactly when the vertices corresponding to $n$ and $m$ have no common edge in $\Gamma^c$, i.e., when they do have a common edge in $\Gamma$.

Thus, $GG(\mathbb{Z}, X) \cong \Gamma$.