What are Graph Powers? [Graph Theory Tutorial]

What are Graph Powers? This video defines graph powers and how you can calculate them yourself.

The K-th power of a graph G is itself a graph with the same vertex set as G, but in which two vertices are adjacent when their distance in G is less than or equal to K. The 2nd power of a graph is known as the square of a graph, and the 3rd power of a graph is known as the cube of a graph. We use exponents next to the name of a graph to denote graph powers. G^3 is the 3rd power of graph G, for example. Powers of graphs are related to taking powers of the adjacency matrices of graphs.

Some interesting properties of graph powers:
If a graph has diameter d, then its d-th power is the complete graph.
The cube of every connected graph contains a hamiltonian cycle.
The square of 2-vertex-connected graphs are always Hamiltonian.

Thanks for watching! If you liked this video, I suggest you check out my graph theory playlist. Here's some links for further exploration:

https://en.wikipedia.org/wiki/Graph_p...
https://mathworld.wolfram.com/GraphPo...
https://www.tau.ac.il/~nogaa/PDFS/cap...

Recommended Books:
******************************* Hypergraph Theory *******************************
"Hypergraph Theory: An Introduction": https://amzn.to/48WKqfy

******************************* Graph Theory *******************************
"Introduction to Graph Theory (Trudeau)": https://amzn.to/48ZWhtj

"Graph Theory (Diestel)": https://amzn.to/4aYCSdW

******************************* Misc. Undergraduate Mathematics *******************************
Discrete Mathematics with Applications (Epp): https://amzn.to/4aWC1dM

A Book of Abstract Algebra (Pinter): https://amzn.to/3S2QmfV

Language, Proof and Logic: https://amzn.to/47EIZkE

Linear Algebra and Its Applications: https://amzn.to/48QsoMt

All the Math You Missed: https://amzn.to/3u5dORP

These are my Amazon Affiliate links. As an Amazon Associate I may earn commissions for purchases made through the links above.

00:00 Definition of Graph Power
06:00 Example 1
07:39 Diameter and Graph Powers