Pebble exchange group of graphs

Abstract: A graph puzzle

m P u z (G)

of a graph

G

is defined as follows. A configuration of

m P u z (G)

is a bijection from the set of vertices of a board graph to the set of vertices of a pebble graph, both graphs being isomorphic to some input graph

G

. A move of pebbles is defined as exchanging two pebbles which are adjacent on both a board graph and a pebble graph. For a pair of configurations

f

and

g

, we say that

f

is equivalent to

g

if

f

can be transformed into

g

by a finite sequence of moves. Let

m A u t (G)

be the automorphism group of

G

, and let

{m 1}_{G}

be the unit element of

m A u t (G)

. The pebble exchange group of

G

, denoted by

m P e b (G)

, is defined as the set of all automorphisms

f

of

G

such that

{m 1}_{G}

and

f

are equivalent to each other. In this paper, some basic properties of

m P e b (G)

are studied. Among other results, it is shown that for any connected graph

G

, all automorphisms of

G

are contained in

m P e b (G^{2})

, where

G^{2}

is a square graph of

G

.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Pebble exchange group of graphs