A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Transitivity of local complementation and switching on graphs
Tekijät: Ehrenfeucht A, Harju T, Rozenberg G
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2004
Lehti:: Discrete Mathematics
Tietokannassa oleva lehden nimi: DISCRETE MATHEMATICS
Lehden akronyymi: DISCRETE MATH
Vuosikerta: 278
Numero: 1-3
Aloitussivu: 45
Lopetussivu: 60
Sivujen määrä: 16
ISSN: 0012-365X
DOI: https://doi.org/10.1016/j.disc.2003.04.001
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali