Abstract:   Given an undirected graph with loops allow,the loop lighting problems is to find a subset of vertices such that pressing the buttons on these vertices will turn on all the lights on loop vertices while keeping other lights off. For a graph which has a loop on everyvertex, the correspon-ding problem is called the all-ones problem.In fact, it can be seen that the loop lighting problem is equivalent to the all ones problem.We present a graph theoretical algorithm to delete a loop vertex of a graph G and to generate a graph H such that a solution of the loop lighting problem for H detemines a solutin for the original graph G, and vice versa.Our algorithm is of polynomial time.

  AMS Classification:   05C85, 05C70, 90C27, 68Q25.

  Keywords:   loop lighting problem, all-ones problem , loop deletion.

  Download:  pdf     ps