science

Graph power

Graph power is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Graph power rather than just read about it. In short: In graph theory, a branch of mathematics, the kth power Gk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc.

Key takeaways

Graph power belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Graph power to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Graph power from memory before moving on to harder problems.

Reference excerpt

In graph theory, a branch of mathematics, the kth power Gk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.

Properties If a graph has diameter d, then its d-th power is the complete graph. If a graph family has bounded clique-width, then so do its d-th powers for any fixed d.

Coloring Graph coloring on the square of a graph may be used to assign frequencies to the participants of wireless communication networks so that no two participants interfere with each other at any of their common neighbors, and to find graph drawings with high angular resolution. Both the chromatic number and the degeneracy of the kth power of a planar graph of maximum degree Δ are O(Δ⌊k/2⌋), where the degeneracy bound shows that a greedy coloring algorithm may be used to color the graph with this many colors. For the special case of a square of a planar graph, Wegner conjectured in 1977 that the chromatic number of the square of a planar graph is at most max(Δ + 5, ⁠3Δ/2⁠ + 1), and it is known that the chromatic number is at most ⁠5Δ/3⁠ + O(1). More generally, for any graph with degeneracy d and maximum degree Δ, the degeneracy of the square of the graph is O(dΔ), so many types of sparse graph other than the planar graphs also have squares whose chromatic number is proportional to Δ. Although the chromatic number of the square of a nonplanar graph with maximum degree Δ may be proportional to Δ2 in the worst case, it is smaller for graphs of high girth, being bounded by O(Δ2 / log Δ) in this case. Determining the minimum number of colors needed to color the square of a graph is NP-hard, even in the planar case.

Hamiltonicity The cube of every connected graph necessarily contains a Hamiltonian cycle. It is not necessarily the case that the square of a connected graph is Hamiltonian, and it is NP-complete to determine whether the square is Hamiltonian. Nevertheless, by Fleischner's theorem, the square of a 2-vertex-connected graph is always Hamiltonian.

Computational complexity The kth power of a graph with n vertices and m edges may be computed in time O(mn) by performing a breadth first search starting from each vertex to determine the distances to all other vertices, or slightly faster using more sophisticated algorithms. Alternatively, If A is an adjacency matrix for the graph, modified to have nonzero entries on its main diagonal, then the nonzero entries of Ak give the adjacency matrix of the kth power of the graph, from which it follows that constructing kth powers may be performed in an amount of time that is within a logarithmic factor of the time for matrix multiplication. The kth powers of trees can be recognized in time linear in the size of the input graph.

Given a graph, deciding whether it is the square of another graph is NP-complete.

Moreover, it is NP-complete to determine whether a graph is a kth power of another graph, for a given number k ≥ 2, or whether it is a kth power of a bipartite graph, for k > 2.

In directed graphs

For the square of directed graphs (or digraphs), each pair of vertices connected by a directed path of length two become connected by a path in the same direction of length one. Pairs of points directed to the same vertex, then, do not cause a connection between them in the square of a directed graph. The second neighborhood problem can be stated in terms of the square of a digraph, asking if there exists a vertex in every oriented graph whose degree increase by at least a factor of two when the graph is squared.

Induced subgraphs

The half-square of a bipartite graph G is the subgraph of G2 induced by one side of the bipartition of G. Map graphs are the half-squares of planar graphs, and halved cube graphs are the half-squares of hypercube graphs. Leaf powers are the subgraphs of powers of trees induced by the leaves of the tree. A k-leaf power is a leaf power whose exponent is k.

References

Illustrations

Worked examples

Example 1 — a first encounter with Graph power

Start with the simplest possible case. Write down what Graph power claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Graph power before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Graph power ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Graph power

In research: Graph power appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Graph power in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Graph power is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph operations, so understanding it makes those chapters shorter.
In everyday life: Look for Graph power outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Graph power” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Graph power in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Graph power means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Graph power out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Graph power in simple terms?

Why does Graph power matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Graph power?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Graph power.