GraphPower returns the kth graph power of a given graph. This is a graph in which two vertices are connected if there exists a path of length at most k in the original graph.

The input graph G may be directed or undirected.

The algorithm adds powers of the adjacency matrix of G and removes any multiple edges.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$P≔\mathrm{PathGraph}\left(5\right)$

$P≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 4\; edges}$

$\mathrm{Edges}\left(P\right)$

$\left\{\left\{1\,2\right\}\,\left\{2\,3\right\}\,\left\{3\,4\right\}\,\left\{4\,5\right\}\right\}$

$\mathrm{DrawGraph}\left(P\,\mathrm{style}=\mathrm{circle}\right)$

$\mathrm{P2}≔\mathrm{GraphPower}\left(P\,2\right)$

$\mathrm{P2}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 7\; edges}$

$\mathrm{Edges}\left(\mathrm{P2}\right)$

$\left\{\left\{1\,2\right\}\,\left\{1\,3\right\}\,\left\{2\,3\right\}\,\left\{2\,4\right\}\,\left\{3\,4\right\}\,\left\{3\,5\right\}\,\left\{4\,5\right\}\right\}$

$\mathrm{DrawGraph}\left(\mathrm{P2}\right)$

$\mathrm{P3}≔\mathrm{GraphPower}\left(P\,3\right)$

$\mathrm{P3}≔\mathrm{Graph\; 3:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 9\; edges}$

$\mathrm{Edges}\left(\mathrm{P3}\right)$

$\left\{\left\{1\,2\right\}\,\left\{1\,3\right\}\,\left\{1\,4\right\}\,\left\{2\,3\right\}\,\left\{2\,4\right\}\,\left\{2\,5\right\}\,\left\{3\,4\right\}\,\left\{3\,5\right\}\,\left\{4\,5\right\}\right\}$

$\mathrm{DrawGraph}\left(\mathrm{P3}\right)$