Returns the specified power of a graph.
The \(k\)-th power of a simple graph \(G = (V, E)\) is the graph \(G^k\) whose vertex set is \(V\), two distinct vertices \(u,v\) are adjacent in \(G^k\) if and only if the shortest path distance between \(u\) and \(v\) in \(G\) is at most \(k\).
- G (graph) – A NetworkX simple graph object.
- k (positive integer) – The power to which to raise the graph \(G\).
\(G\) to the \(k\)-th power.
NetworkX simple graph
ValueError– If the exponent \(k\) is not positive.
NetworkXError– If G is not a simple graph.
>>> G = nx.path_graph(4) >>> nx.power(G,2).edges() [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] >>> nx.power(G,3).edges() [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
A complete graph of order n is returned if k is greater than equal to n/2 for a cycle graph of even order n, and if k is greater than equal to (n-1)/2 for a cycle graph of odd order.
>>> G = nx.cycle_graph(5) >>> nx.power(G,2).edges() == nx.complete_graph(5).edges() True >>> G = nx.cycle_graph(8) >>> nx.power(G,4).edges() == nx.complete_graph(8).edges() True
- Bondy, U. S. R. Murty, Graph Theory. Springer, 2008.
Exercise 3.1.6 of Graph Theory by J. A. Bondy and U. S. R. Murty .