Induced path

Article summary

. Finding the longest induced path in a hypercube is known as the snake-in-the-box problem. In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge in , and each two nonadjacent vertices in the sequence are not connected by any edge in . An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem. Similarly, an induced cycle is a cycle that is an induced subgraph of ; induced cycles are also called chordless cycles or (when the length of the cycle is four or more) holes. An antihole is a hole in the complement of , i.e., an antihole is a complement of a hole. The length of the longest induced path in a graph has sometimes been called the detour number of the graph; for sparse graphs, having bounded detour number is equivalent to having bounded tree-depth. The induced path number of a graph is the smallest number of induced paths into which the vertices of the graph may be partitioned, and the closely related path cover number of is the smallest number of induced paths that together include all vertices of .…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.