Graph Power

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

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

which counts all paths of length up to  (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  (Skiena 1990, p. 253).

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.