Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.operators.product.power

power(G, k)

Returns the specified power of a graph.

The \(k`th power of a simple graph :math:`G\), denoted \(G^k\), is a graph on the same set of nodes in which two distinct nodes \(u\) and \(v\) are adjacent in \(G^k\) if and only if the shortest path distance between \(u\) and \(v\) in \(G\) is at most \(k\).

Parameters:

• G (graph) – A NetworkX simple graph object.
• k (positive integer) – The power to which to raise the graph G.

Returns:

G to the power k.

Return type:

NetworkX simple graph

Raises:

• ValueError – If the exponent k is not positive.
• NetworkXNotImplemented – If G is not a simple graph.

Examples

The number of edges will never decrease when taking successive powers:

>>> G = nx.path_graph(4)
>>> list(nx.power(G, 2).edges)
[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
>>> list(nx.power(G, 3).edges)
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

The k`th power of a cycle graph on *n* nodes is the complete graph on *n* nodes, if `k is at least n // 2:

>>> G = nx.cycle_graph(5)
>>> H = nx.complete_graph(5)
>>> nx.is_isomorphic(nx.power(G, 2), H)
True
>>> G = nx.cycle_graph(8)
>>> H = nx.complete_graph(8)
>>> nx.is_isomorphic(nx.power(G, 4), H)
True

References

[1]	Bondy, U. S. R. Murty, Graph Theory. Springer, 2008.

Notes

This definition of “power graph” comes from Exercise 3.1.6 of Graph Theory by Bondy and Murty [1].