Lit-only sigma game on a line graph (Q2519798): Difference between revisions

Let \(\Gamma \) be a connected graph and \(V(\Gamma )\) its vertex set. Denote by \(\mathbb{F}\) the set of functions from \(V(\Gamma )\) to the binary field \(\mathbb{F}_{2}\). For any \(x\in \mathbb{F}\), a move of the lit-only sigma game on \(\Gamma \) consists of choosing some vertex \(v\) with \(x(v)=1\) and changing the values of \(x\) at all those neighbors of \(v\). An orbit is a maximal subset of \(\mathbb{F}\) satisfying the property that any two elements can reach each other by a series of moves. The minimum light number of \(\Gamma \) is \(\max_{K}\min_{x\in K}\#\text{supp}(x)\), where \(K\) runs through all orbits. It is shown that the minimum light number of the line graph of \(\Gamma \) is equal to \(\max \{b(\Gamma ),\rho (\sigma ^{1}(\Gamma ))\}\), where \(b(\Gamma )\) is the isoperimetric number of \(\Gamma \) and \(\rho (\sigma ^{1}(\Gamma ))\) is the covering radius of the subspace of set of functions from \(E(\Gamma )\) (the set of edges of \(\Gamma \)) to the binary field \(\mathbb{F}_{2}\) generated by the rows of the adjacency matrix of \(L(\Gamma )\). The sizes of all orbits of the lit-only sigma game on \(L(\Gamma )\) are also determined. It is also shown that when \(\Gamma \) is a tree, the minimum light number of \(L(\Gamma )\) is \(b(\Gamma )\). Furthermore, it is shown that, if the tree has \(n\geq 3\) vertices, the group formed by the moves of the lit-only sigma game on \(L(\Gamma )\) is the symmetric group on \(n \) elements.