Atlas home || Conferences | Abstracts | about Atlas

22nd Cumberland Conference on Combinatorics, Graph Theory and Computing
May 21-23, 2009
Western Kentucky University
Bowling Green, KY, USA

Organizers
Bela Csaba, Chair; Mustafa Atici; Robert Crawford; Claus Ernst; Dominic Lanphier; Attila Por

View Abstracts
Conference Homepage

Lit-only and regular switching in a graph
by
John Goldwasser
West Virginia University
Coauthors: Xinmao Wang, USTC, Hefei, China; Yaokun Wu, Shanghai Jiaotong University, China

Each vertex in a graph is on or off. In the open (closed) sigma-game, you can "toggle" a vertex v which changes the state of each vertex in the open (closed) neighborhood of v. The object is to mimimize the number of on vertices by a sequence of toggles. In the lit-only versions of these games, only on vertices can be toggled. We show this restriction makes essentially no difference in the closed neighborhood game, but a big difference in the open neighborhood game.

Date received: April 27, 2009

Copyright © 2009 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cayq-46.