Metraipolis › archive › dc_31aa6be5e950

Induced path — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Induced_path
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-07T18:21:28.980Z
SHA-256 of the archived text
2895268c55da37e724126ae2b2a88e17897ba65aa3a71a6444b25c171c6a5aec
Stable URL of this page
https://metraipolis.com/documento/dc_31aa6be5e950

How to cite

Induced path — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Induced_path (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_31aa6be5e950 (Metraipolis archive dc_31aa6be5e950, sha256 2895268c55da37e724126ae2b2a88e17897ba65aa3a71a6444b25c171c6a5aec)
BibTeX
@misc{dc31aa6be5e950,
  title = {Induced path — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Induced_path},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_31aa6be5e950; sha256 2895268c55da37e724126ae2b2a88e17897ba65aa3a71a6444b25c171c6a5aec},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Induced_path. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. 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 G; 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 G, 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 G 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 G is the smallest number of induced paths that together include all vertices of G. The girth of a graph is the length of its shortest cycle, but this cycle must be an induced cycle as any chord could be used to produce a shorter cycle; for similar reasons the odd girth of a graph is also the length of its shortest odd induced cycle.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Induced path» — https://en.wikipedia.org/wiki/Induced_path
Wikidata Q15704639: «graph path which is an induced subgraph» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q15704639
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Induced_path?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1335627072, consultata il 2026-11-07T18:15:07.196Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e78c2beb930325ee62882c937dfb9445fc7b76a1e37aa6804f2a49f724715b9b