# edge covering

Let $G$ be a graph. An *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 vertex set is a trivial edge covering. Generally, we are more interested in *minimal coverings*. A minimal edge covering is simply an edge covering of the least possible .

Title | edge covering |
---|---|

Canonical name | EdgeCovering |

Date of creation | 2013-03-22 12:40:02 |

Last modified on | 2013-03-22 12:40:02 |

Owner | vampyr (22) |

Last modified by | vampyr (22) |

Numerical id | 8 |

Author | vampyr (22) |

Entry type | Definition |

Classification | msc 05C70 |

Related topic | Matching |

Defines | minimal edge covering |