Lit-only sigma game on a line graph

Let ΓΓ be a connected graph. For any x∈F2V(Γ), a move of the lit-only sigma game on ΓΓ consists of choosing some v∈V(Γ)v∈V(Γ) with x(v)=1x(v)=1 and changing the values of xx at all those neighbors of vv. An orbit is a maximal subset of F2V(Γ) any two of which can reach each other by a series of moves. The minimum light number of ΓΓ is maxKminx∈K#supp(x)maxKminx∈K#supp(x), where KK runs through all orbits.Denote by L(Γ)L(Γ) the line graph of ΓΓ. The subspace of F2E(Γ) that is generated by the rows of the adjacency matrix of L(Γ)L(Γ) is dubbed σ1(Γ)σ1(Γ). We view σ1(Γ)σ1(Γ) as a linear code in F2E(Γ) and let ρ(σ1(Γ))ρ(σ1(Γ)) be the covering radius of σ1(Γ)σ1(Γ). For any S⊆V(Γ)S⊆V(Γ), the edge-boundary of SS is the set EB(S)EB(S) of edges with exactly one endpoint lying inside SS. The edge isoperimetric number of ΓΓ, denoted b(Γ)b(Γ), is defined to be maxkmin#S=k#EB(S)maxkmin#S=k#EB(S).The main result of this note is that the minimum light number of L(Γ)L(Γ) is equal to max{ρ(σ1(Γ)),b(Γ)}max{ρ(σ1(Γ)),b(Γ)}. We also determine the sizes of all orbits of the lit-only sigma game on L(Γ)L(Γ). Especially, when ΓΓ is a tree, we prove that the minimum light number of L(Γ)L(Γ) is b(Γ)b(Γ). Moreover, if the tree ΓΓ has n≥3n≥3 vertices, the group formed by the moves of the lit-only sigma game on L(Γ)L(Γ) is shown to be the symmetric group on nn elements.