TY - JOUR

T1 - The edge-flipping group of a graph

AU - Huang, Hau wen

AU - Weng, Chih wen

N1 - Funding Information:
Research partially supported by the NSC grant 97-2115-M-009-002 of Taiwan, ROC.

PY - 2010/4

Y1 - 2010/4

N2 - Let X = (V, E) be a finite simple connected graph with n vertices and m edges. A configuration is an assignment of one of the two colors, black or white, to each edge of X. A move applied to a configuration is to select a black edge ε{lunate} ∈ E and change the colors of all adjacent edges of ε{lunate}. 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 X, and it corresponds to a group action. This group is called the edge-flipping group WE (X) of X. This paper shows that if X has at least three vertices, WE (X) is isomorphic to a semidirect product of (Z / 2 Z)k and the symmetric group Sn of degree n, where k = (n - 1) (m - n + 1) if n is odd, k = (n - 2) (m - n + 1) if n is even, and Z is the additive group of integers.

AB - Let X = (V, E) be a finite simple connected graph with n vertices and m edges. A configuration is an assignment of one of the two colors, black or white, to each edge of X. A move applied to a configuration is to select a black edge ε{lunate} ∈ E and change the colors of all adjacent edges of ε{lunate}. 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 X, and it corresponds to a group action. This group is called the edge-flipping group WE (X) of X. This paper shows that if X has at least three vertices, WE (X) is isomorphic to a semidirect product of (Z / 2 Z)k and the symmetric group Sn of degree n, where k = (n - 1) (m - n + 1) if n is odd, k = (n - 2) (m - n + 1) if n is even, and Z is the additive group of integers.

UR - http://www.scopus.com/inward/record.url?scp=75149183117&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2009.06.004

DO - 10.1016/j.ejc.2009.06.004

M3 - 期刊論文

AN - SCOPUS:75149183117

SN - 0195-6698

VL - 31

SP - 932

EP - 942

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 3

ER -