TOPICS
Search

Graph Power


GraphPower

The kth power of a graph G is a graph with the same set of vertices as G and an edge between two vertices iff there is a path of length at most k between them (Skiena 1990, p. 229). Since a path of length two between vertices u and v exists for every vertex w such that {u,w} and {w,v} are edges in G, the square of the adjacency matrix of G counts the number of such paths. Similarly, the (u,v)th element of the kth power of the adjacency matrix of G gives the number of paths of length k between vertices u and v. Graph powers are implemented in the Wolfram Language as GraphPower[g, k].

The graph kth power is then defined as the graph whose adjacency matrix given by the sum of the first k powers of the adjacency matrix,

 adj(G^k)=sum_(i=1)^k[adj(G)]^i,

which counts all paths of length up to k (Skiena 1990, p. 230).

Raising any graph to the power of its graph diameter gives a complete graph. The square of any biconnected graph is Hamiltonian (Fleischner 1974, Skiena 1990, p. 231). Mukhopadhyay (1967) has considered "square root graphs," whose square gives a given graph G (Skiena 1990, p. 253).


See also

Adjacency Matrix, Graph Cube, Graph Square, Pósa's Theorem, Seymour Conjecture

Explore with Wolfram|Alpha

References

Fleischner, H. "The Square of Every Two-Connected Graph Is Hamiltonian." J. Combin. Th. Ser. B 16, 29-34, 1974.Mukhopadhyay, A. "The Square Root of a Graph." J. Combin. Th. 2, 290-295, 1967.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Referenced on Wolfram|Alpha

Graph Power

Cite this as:

Weisstein, Eric W. "Graph Power." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphPower.html

Subject classifications