About: Saturation (graph theory)

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Given a graph , another graph is -saturated if does not contain a (not necessarily induced) copy of , but adding any edge to it does. The function is the minimum number of edges an -saturated graph on vertices can have. For some results, see https://faculty.math.illinois.edu/~west/regs/saturate.html. In matching theory, there is a different definition.Let be a graph and a matching in . A vertex is said to be saturated by if there is an edge in incident to . A vertex with no such edge is said to be unsaturated by . We also say that saturates .

Property Value
dbo:abstract
  • Given a graph , another graph is -saturated if does not contain a (not necessarily induced) copy of , but adding any edge to it does. The function is the minimum number of edges an -saturated graph on vertices can have. For some results, see https://faculty.math.illinois.edu/~west/regs/saturate.html. In matching theory, there is a different definition.Let be a graph and a matching in . A vertex is said to be saturated by if there is an edge in incident to . A vertex with no such edge is said to be unsaturated by . We also say that saturates . (en)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 2547402 (xsd:integer)
dbo:wikiPageLength
  • 1193 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1123416665 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • Given a graph , another graph is -saturated if does not contain a (not necessarily induced) copy of , but adding any edge to it does. The function is the minimum number of edges an -saturated graph on vertices can have. For some results, see https://faculty.math.illinois.edu/~west/regs/saturate.html. In matching theory, there is a different definition.Let be a graph and a matching in . A vertex is said to be saturated by if there is an edge in incident to . A vertex with no such edge is said to be unsaturated by . We also say that saturates . (en)
rdfs:label
  • Saturation (graph theory) (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License