Suppose $G = (V, E)$ is a finite undirected simple graph. Let’s, define the $n$-th power of a graph (where $n \in \mathbb{N}$) as graph $G^n = (V, E_n)$, where $$E_n = \begin{cases} E & \quad n = 1 \\ \{\{v, w\} \in P(V)|v \neq w \text{ and } \exists u \in V, \{v, u\} \in E_{n - 1}, \{u, w\} \in E \} & \quad n > 1 \end{cases}$$
Let’s call a graph $G$ power-invariant iff $\forall n \in \mathbb{N}$, $G$ is isomorphic to $G^n$.
Is there a way to classify all power-invariant graphs?
I know, that all full graphs $K_n$ with $n \geq 3$ are power-invariant, however, I have heard of neither other examples of power invariant graphs, nor proofs that there aren’t ones.
It's obvious (or, if not, at least easy to show) that this property is closed under disjoint union, so the interesting question is to characterise the irreducible finite power-invariant graphs.
In addition to complete graphs $K_n$ for $n \ge 3$ we can list the trivial graph $K_1$. We can also observe that all odd cycles $C_{2a+1}$ satisfy $G^2 \approx G$, but they aren't power-invariant for $2a+1 > 3$ because $G^3$ is regular with degree 4.
Each connected component of a finite power-invariant graph must remain a single connected component when raised to any power. Proof: if $C$ is a connected component of a finite power-invariant graph $G$ and $C^k$ has more than one connected component, $G^k$ must have more connected components than $G$. (Clearly two connected components of $G$ won't merge into one connected component of $G^k$ to compensate). But that contradicts the assumption that $G$ is power-invariant.
If $C$ is a connected component of a finite power-invariant graph $G$, there must be some $k > 1$ such that $C^k$ is isomorphic to $C$. Proof: consider the directed (non-simple, because it may have loops) graph $\Gamma$ whose vertices are graphs with the same number of vertices as $C$ and where each vertex $V$ has one edge, to $V^2$. $\Gamma$ is finite and each of its connected components is a finite cycle or loop with zero or more inverted trees feeding into it. If there is no $k > 1$ such that $C^k \approx C$ then $C$ cannot be in a cycle. Now, $G^2 \approx G$, so $G$ must contain a connected component $C'$ such that $C'^2 \approx C$, or $C' \to C$ in $\Gamma$. Similarly, it must contain a connected component $C'' \to C'$, etc. But because $C$ is an internal node of a finite tree, we can't chain backwards indefinitely.
Define the order of $C$ as the smallest $k > 1$ such that $C^k \approx C$.
If $C$ is a connected component of a finite power-invariant graph $G$, $C^2$ is isomorphic to $C$. Proof: we know that each connected component of $G$ has a finite order. Suppose $C$ is a connected component of $G$ with order $k$. Since $G \approx G^a$ for each $a \in \{1, \ldots, k-1\}$, $G$ contains a connected component isomorphic to $C^a$ for each $a \in \{1, \ldots, k-1\}$. None of these connected components can be isomorphic to each other without contradicting the definition of $k$ as the order of $C$.
Let $p$ be a prime factor of $k-1$. In $G^p$ these connected components become $G^p, G^{2p}, \ldots, G^{(k-1)p}$, which are $p$ copies each of $\frac{k-1}{p}$ isomorphically distinct connected components. In particular, $(C^{k-1})^p \approx C^{k-1}$. Therefore the number of copies of $C^{k-1}$ in $G^p$ is at least as many as the number of copies of both $C^{(k-1)/p}$ and $C^{k-1}$ in $G$. Since there's at least one copy of $C^{(k-1)/p}$, $G$ is either not finite or not isomorphic to $G^p$.
Therefore $k-1$ must be coprime to all primes, so $k-1 = 1$ and $k=2$.
Corollary: the irreducible finite power-invariant graphs consist of a single connected component.
Suppose $G$ is a connected finite power-invariant graph. Then it is a complete graph.
Proof: the only connected graphs on fewer than three vertices are complete graphs, so there is nothing to prove in those cases and we need only consider the case that $G$ has at least three vertices. $G$ cannot be bipartite, for then $G^2$ would not be connected, so $G$ must contain an odd cycle $u_1 \to u_2 \to \cdots \to u_{2k+1} \to u_1$. For all $a \ge 2k$ there is a trail $u_1 \to^a u_{2k+1}$: if $a$ is even then the trail goes $u_1 \to u_2 \to \cdots \to u_{2k+1} (\to u_{2k} \to u_{2k+1})^{a-2k}$, and if $a$ is odd then the trail goes $u_1 \to u_{2k+1} (\to u_{2k} \to u_{2k+1})^{a-1}$. It follows that if we consider two arbitrary vertices $v$ and $w$ then $\{v,w\} \in E_{2n+2k-2}$: there is a path $v \to^i u_1$ for some $i \le n-1$, a path $u_{2k+1} \to^j w$ for some $j \le n-1$, and a trail $u_1 \to^{2k+(n-1-i)+(n-1-j)} u_{2k+1}$. Therefore $G^{2n+2k-2} \approx K_n$.