0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – hbm Apr 19 at 8:44
  • $\begingroup$ @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. $\endgroup$ – bof Apr 19 at 11:49
  • $\begingroup$ 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\}$. $\endgroup$ – bof Apr 19 at 11:55
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Taylor Apr 21 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.