Graph Power

Author

Eric W. Weisstein
July 25, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/GraphPower.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/GraphPower.html.

©2024 Wolfram Research, Inc. except for portions noted otherwise

Figure

Built-in

gs={"FruchtGraph",{"Grid",{3,5}},"DodecahedralGraph"};

RecognizeGraph[GraphPower[GraphData[#],2]]&/@{"FruchtGraph",{"Grid",{3,5}},"DodecahedralGraph","IcosahedralGraph"}

Grid[Prepend[
Flatten/@Thread[{GraphData[#,"Name"]&/@gs,StyleGraphs/@Outer[GraphPower,GraphData/@gs,Range[3]]}],
Prepend[Table[Row[{Style["k",Italic],"==",n}," "],{n,3}],""]],BaseStyle->Directive[14,FontFamily->"Times"],Dividers->All]

Definition

Graph

dodec=GraphData["DodecahedralGraph"]

MyGraphPower[g_Graph,n_]:=With[{adj=AdjacencyMatrix[g]},AdjacencyGraph[Total[NestList[adj.#&,adj,n-1]]]//SimpleGraph]

MyGraphPower[dodec,2]

RecognizeGraph@%

Square

dodec2=GraphPower[dodec,2]

RecognizeGraph@dodec2

adj=AdjacencyMatrix[dodec]

AdjacencyGraph[adj+adj.adj]//SimpleGraph

RecognizeGraph@%

Cube

dodec3=GraphPower[dodec,3]

RecognizeGraph@dodec3

adj=AdjacencyMatrix[dodec]

AdjacencyGraph[adj+adj.adj+adj.adj.adj]//SimpleGraph

RecognizeGraph@%