# Is there a way to classify all power-invariant graphs?

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.

• Note that if $G$ is connected then there is a $d \gt 0$ such that $G^d \cong K_n$ where $n$ is the number of vertices – hbm Apr 19 at 8:44
• @hbm If $G^d$ is defined in the usual way, $G^d$ is a complete graph whenever $d\ge\operatorname{diam}(G)$. However, under the OP's peculiar definition, if $G$ is a bipartite graph, then $G^d$ is bipartite whenever $d$ is odd. – bof Apr 19 at 11:49
• According to your (unusual) definition of $G^n$, the complete graph $K_2$ is not power-invariant. If $G$ has two vertices $v,w$ one one edge $\{v,w\}$, then your $G^2$ has two loop-edges $\{v,v\}$ and $\{w,w\}$, but no edge $\{v,w\}$. – bof Apr 19 at 11:55

## 1 Answer

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$$.

• Interesting follow-up question: for what connected graphs do we have $G \approx G^2$? They clearly include the power-invariant complete graphs and the odd cycles, and up to 15 vertices there are no others. – Peter Taylor Apr 21 at 8:17