Transitivity of local complementation and switching on graphs

: Ehrenfeucht A, Harju T, Rozenberg G

Publisher: ELSEVIER SCIENCE BV

: 2004

Discrete Mathematics

DISCRETE MATHEMATICS

: DISCRETE MATH

: 278

: 1-3

: 45

: 60

: 16

: 0012-365X

DOI: https://doi.org/10.1016/j.disc.2003.04.001

The operations complementation C, local complementation lambda(x), and switching sigma(x) for the vertices x of a finite undirected graph are considered. The operation, complements the subgraph induced by the neighbourhood of x in the given graph, and the switching a, changes the neighbourhood of x to its complement vertex set. It is proved that the compositions delta(x) = lambda(x)C (for vertices x is an element of D) generate a transitive group on the graphs with vertex set D, that is, for any two graphs g and h on D, there exists a composition a of operations 6, such that h = a(g). It is also shown that the compositions tau(x) = lambda(x)sigma(x) (for x is an element of D) generate a transitive group on the graphs. (C) 2003 Elsevier B.V. All rights reserved.

Mathematics