The th power of a graph joins distinct vertices whenever their distance in the original graph is at most . For example, the square of a cycle adds edges connecting vertices two steps apart. Graph powers turn constraints on short paths into adjacency constraints.
In a cycle square, each triple of consecutive vertices is a clique. A proper three-colouring therefore repeats with period three and closes exactly when the length is divisible by three. For all other cycle lengths at least four colours are needed; the five-cycle square is a complete five-vertex graph.
Articles by others on the same topic
"Graph power" is not a standard term in mathematics or computer science, so it may refer to different concepts depending on the context. Here are some interpretations: 1. **Graph Theory**: In the context of graph theory, "power" can refer to the concept of a power of a graph, which is related to the construction of new graphs by connecting vertices based on paths of a certain length.