Extremal Graphs for the Lights Out Problem
Lights Out is a game played on a graph $G$ where every vertex has a light bulb that is either on or off, and pressing a vertex $v$ toggles the state of every vertex in the closed neighborhood of $v$. The goal is to find a subset of vertices $S$ such that pressing every vertex in $S$ results in all light bulbs being turned off. We study the extremal graphs for which pressing every vertex is the unique solution to the lights out problem given an initial configuration of all lights on. We show that a graph is extremal if and only if it is even and has an odd number of matchings. Furthermore,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.07241
curl -X POST /api/v1/records/arxiv/2602.07241/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.07241/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'