A1 Refereed original research article in a scientific journal
Transitivity of local complementation and switching on graphs
Authors: Ehrenfeucht A, Harju T, Rozenberg G
Publisher: ELSEVIER SCIENCE BV
Publication year: 2004
Journal:: Discrete Mathematics
Journal name in source: DISCRETE MATHEMATICS
Journal acronym: DISCRETE MATH
Volume: 278
Issue: 1-3
First page : 45
Last page: 60
Number of pages: 16
ISSN: 0012-365X
DOI: https://doi.org/10.1016/j.disc.2003.04.001
Abstract
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.
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.
UTU Research Portal