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