Metraipolis › archive › dc_40becb4ef5f1

Saturation (graph theory) — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Saturation_(graph_theory)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T17:34:08.088Z
SHA-256 of the archived text
739d29a2206a894b64900fde7d58d01bdfc86adb3753ca60f6ea1e7ce5163c90
Stable URL of this page
https://metraipolis.com/documento/dc_40becb4ef5f1

How to cite

Saturation (graph theory) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Saturation_(graph_theory) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_40becb4ef5f1 (Metraipolis archive dc_40becb4ef5f1, sha256 739d29a2206a894b64900fde7d58d01bdfc86adb3753ca60f6ea1e7ce5163c90)
BibTeX
@misc{dc40becb4ef5f1,
  title = {Saturation (graph theory) — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Saturation_(graph_theory)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_40becb4ef5f1; sha256 739d29a2206a894b64900fde7d58d01bdfc86adb3753ca60f6ea1e7ce5163c90},
  year = {2026}
}

Archived text

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

In extremal graph theory, given a graph H {\displaystyle H} , a graph G {\displaystyle G} is said to be H {\displaystyle H} -saturated if G {\displaystyle G} does not contain a copy of H {\displaystyle H} as a subgraph, but adding any edge to G {\displaystyle G} creates a copy of H {\displaystyle H} . The saturation number, denoted sat ( n , H ) {\displaystyle \operatorname {sat} (n,H)} , is the minimum number of edges in an H {\displaystyle H} -saturated graph on n {\displaystyle n} vertices. The graph saturation problem is the problem of determining sat ( n , H ) {\displaystyle \operatorname {sat} (n,H)} for all graphs H {\displaystyle H} and positive integers n {\displaystyle n} . The saturation number was introduced in 1964 by Erdős, Hajnal, and Moon as a dual to the extremal number ex ( n , H ) {\displaystyle \operatorname {ex} (n,H)} . The extremal number ex ( n , H ) {\displaystyle \operatorname {ex} (n,H)} is the maximum number of edges in an H {\displaystyle H} -saturated graph on n {\displaystyle n} vertices; this is equivalent to its original definition as the maximum number of edges in an n {\displaystyle n} -vertex graph with no copy of H {\displaystyle H} .

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Saturation (graph theory)» — https://en.wikipedia.org/wiki/Saturation_(graph_theory)
Wikidata Q7426587 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q7426587
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Saturation_(graph_theory)?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 1318278744, consultata il 2026-10-06T16:01:04.200Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e014e93358a8a6b7c51fc2e478a8ad802f47a834df142235690f3ec7d2da5a73