Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654125 | European Journal of Combinatorics | 2010 | 11 Pages |
Let X=(V,E)X=(V,E) be a finite simple connected graph with nn vertices and mm edges. A configuration is an assignment of one of the two colors, black or white, to each edge of XX. A move applied to a configuration is to select a black edge ϵ∈Eϵ∈E and change the colors of all adjacent edges of ϵϵ. Given an initial configuration and a final configuration, try to find a sequence of moves that transforms the initial configuration into the final configuration. This is the edge-flipping puzzle on XX, and it corresponds to a group action. This group is called the edge-flipping group WE(X) of XX. This paper shows that if XX has at least three vertices, WE(X) is isomorphic to a semidirect product of (Z/2Z)k(Z/2Z)k and the symmetric group SnSn of degree nn, where k=(n−1)(m−n+1)k=(n−1)(m−n+1) if nn is odd, k=(n−2)(m−n+1)k=(n−2)(m−n+1) if nn is even, and ZZ is the additive group of integers.