Minimum light numbers in the -game and lit-only -game on unicyclic and grid graphs
Minimum light numbers in the \(\sigma \)-game and lit-only \(\sigma \)-game on unicyclic and grid graphs
Summary: Consider a graph each of whose vertices is either in the ON state or in the OFF state and call the resulting ordered bipartition into ON vertices and OFF vertices a configuration of the graph. A regular move at a vertex changes the states of the neighbors of that vertex and hence sends the current configuration to another one. A valid move is a regular move at an ON vertex. For any graph \(G\), let \(\mathcal D(G)\) be the minimum integer such that given any starting configuration \(x\) of \(G\) there must exist a sequence of valid moves which takes \(x\) to a configuration with at most \(\ell + \mathcal D(G)\) ON vertices provided there is a sequence of regular moves which brings x to a configuration in which there are \(\ell\) ON vertices. The shadow graph \(\mathcal S(G)\) of a graph \(G\) is obtained from \(G\) by deleting all loops. We prove that \(\mathcal D(G) \leq 3\) if \(\mathcal S(G)\) is unicyclic and give an example to show that the bound 3 is tight. We also prove that \(\mathcal D(G) \leq 2\) if \(G\) is a two-dimensional grid graph and \(\mathcal D(G) = 0\) if \(\mathcal S(G)\) is a two-dimensional grid graph but not a path and \(G \neq \mathcal S(G)\).
- Lit-only sigma-game on nondegenerate graphs
- Maximum orbit weights in the -game and lit-only -game on grids and graphs
- scientific article; zbMATH DE number 1161323
- Lightness of digraphs in surfaces and directed game chromatic number
- On the game domination number of graphs with given minimum degree
- Lit-only \(\sigma \)-game on pseudo-trees
- A polynomial bound on the number of light cycles in an undirected graph
- Completely symmetric configurations for \(\sigma \)-games on grid graphs
- The game \(L(d,1)\)-labeling problem of graphs
- Minimum degree games for graphs
- Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
- Maximum orbit weights in the -game and lit-only -game on grids and graphs
- Two-lit trees for lit-only \(\sigma \)-game
- Lit-only sigma-game on nondegenerate graphs
- Lit-only sigma game on a line graph
- Orbits under dual symplectic transvections
- Completely symmetric configurations for \(\sigma \)-games on grid graphs
This page was built for publication: Minimum light numbers in the \(\sigma \)-game and lit-only \(\sigma \)-game on unicyclic and grid graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648407)
