The edge-flipping group of a graph

Hau wen Huang*, Chih-wen Weng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)932-942
Number of pages11
JournalEuropean Journal of Combinatorics
Volume31
Issue number3
DOIs
StatePublished - Apr 2010

Fingerprint

Dive into the research topics of 'The edge-flipping group of a graph'. Together they form a unique fingerprint.

Cite this