edge covering EdgeCovering 2002-05-26 03:08:37 2002-07-06 13:48:36 Definition minimal edge covering % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here Let $G$ be a graph. An \emph{edge covering} $C$ on $G$ is a subset of the vertices of $G$ such that each edge in $G$ is incident with at least one vertex in $C$. For any graph, the \PMlinkescapeword{entire} vertex set is a trivial edge covering. Generally, we are more interested in \emph{minimal coverings}. A minimal edge covering is simply an edge covering of the least possible \PMlinkescapeword{size}.