vertex cover

顶点覆盖

Combinatorics · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Translation evidence: Literature usage

Meaning in context

A vertex cover of a simple graph G is a vertex subset C such that every edge of G has at least one endpoint in C.

简单图的顶点覆盖是顶点子集 C，使图中每条边至少有一个端点属于 C。

Example

In $a-b-c-d$, $\{b,c\}$ covers all three edges.

Usage and distinctions

A vertex cover meets every edge; a dominating set need only meet or neighbor every vertex. No minimality is implied by the word cover.

Recommended reading in this subject · Preparation & skip guidance

Definition sources

1. Reinhard Diestel — Graph Theory, fourth electronic edition (2010), corrected reprint 2012Section 2.1, vertex cover definition immediately before Theorem 2.1.1 · Checked 2026-10-14

Translation sources

1. Reinhard Diestel — 图论，第五版，于青林译§2.1，印刷p.34，定理2.1.1前「（顶点）覆盖」定义及定理中的「顶点覆盖」 · Checked 2026-10-14

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.