Graph Power — Definition, Formula & Examples

Graph power is an operation that creates a new graph from an existing one by connecting every pair of vertices whose distance in the original graph is at most a specified value k.

Given a graph $G = (V, E)$ and a positive integer $k$ , the $k$ -th power of $G$ , denoted $G^k$ , is the graph on the same vertex set $V$ where two distinct vertices $u$ and $v$ are adjacent in $G^k$ if and only if the shortest path distance $d_G(u, v) \leq k$ .

Key Formula

E(G^k) = \{\{u, v\} : u, v \in V,\; u \neq v,\; d_G(u, v) \leq k\}

Where:

$G^k$ = The k-th power of graph G
$V$ = Vertex set of the original graph G
$d_G(u, v)$ = Shortest path distance between u and v in G
$k$ = Positive integer specifying the maximum distance for adjacency

How It Works

To construct

G^k

, start with the same set of vertices as

G

. For each pair of vertices, compute their shortest path distance in

G

. If that distance is

k

or less, draw an edge between them in

G^k

. The original edges of

G

(distance 1) are always preserved, and new edges are added for vertices reachable in 2, 3, ..., up to

k

steps. Note that

G^1 = G

, and as

k

increases,

G^k

becomes denser, eventually becoming a complete graph when

k

equals or exceeds the diameter of

G

Worked Example

Problem: Let G be the path graph on 4 vertices:

v_1 - v_2 - v_3 - v_4

. Find

G^2

Step 1: List all pairwise distances in G.

d(v_1,v_2)=1,\; d(v_1,v_3)=2,\; d(v_1,v_4)=3,\; d(v_2,v_3)=1,\; d(v_2,v_4)=2,\; d(v_3,v_4)=1

Step 2: Include an edge in

G^2

for every pair with distance at most 2.

E(G^2) = \{\{v_1,v_2\},\{v_1,v_3\},\{v_2,v_3\},\{v_2,v_4\},\{v_3,v_4\}\}

Step 3: The pair

\{v_1, v_4\}

has distance 3, which exceeds 2, so it is not an edge in

G^2

Answer:

G^2

has 5 edges. Compared to the original 3 edges, two new edges (

\{v_1,v_3\}

and

\{v_2,v_4\}

) were added.

Why It Matters

Graph powers appear in frequency assignment problems for wireless networks, where transmitters within

k

hops of each other must use different channels. They also play a role in graph coloring theory — a classical result states that the cube of every connected graph is Hamiltonian.

Common Mistakes

Mistake: Confusing graph power

G^k

with the Cartesian or tensor product of

G

with itself

k

times.

Correction: Graph power keeps the same vertex set and adds edges based on distance. Graph products create a new, larger vertex set from ordered tuples. These are fundamentally different operations.