A subset of a graph for which no two points are adjacent

  • point coverage
  • A set of subpoints S of a graph, where any edge of the graph is connected to a point contained in S

For bipartite graphs, Minimum Point Coverage and Maximum matching have the same size.

In general graphs, the number of vertices in the graph itself is obtained by adding the number of vertices in the minimum point cover and the maximum stable set


This page is auto-translated from /nishio/安定集合 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.