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 -