Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to place light bulbs on some vertices (each bulb will lit up every edges it connected) where all edges lit up.

e.g. suppose I have this simple planar graph,

7-wheel graph

Sufficient vertices to place those light bulbs are $\{0, 1, 3, 5\}$.

At first I think this is art gallery problem, but they focus on seeing every vertices, not edges. Or I need some kind of graph transformation to fit my problem into it?

share|cite|improve this question
Looks like you're looking for a vertex cover. – EuYu Mar 13 '13 at 1:20
I must confess, since I'm from non-English spoken country, I think the problem name should be edge covered. XD – neizod Mar 13 '13 at 1:45
Well, a vertex cover has vertices as the "covers". The edge covering problem is the other way around: You find a set of edges in which every vertex is adjacent to at least one edge. The problems seem similar but are very different in terms of difficulty. In summary: If you want to light up edges using vertices, you want a vertex cover. If you want to light up vertices using edges, you want an edge cover. – EuYu Mar 13 '13 at 1:54
up vote 3 down vote accepted

Maybe you are looking for the minimum vertex cover problem? This document contains some information about the restriction of the problem to planar graphs.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.