A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Acyclicity of switching classes
Tekijät: Hage J, Harju T
Kustantaja: ACADEMIC PRESS LTD
Julkaisuvuosi: 1998
Lehti:: European Journal of Combinatorics
Tietokannassa oleva lehden nimi: EUROPEAN JOURNAL OF COMBINATORICS
Lehden akronyymi: EUR J COMBIN
Vuosikerta: 19
Numero: 3
Aloitussivu: 321
Lopetussivu: 327
Sivujen määrä: 7
ISSN: 0195-6698
DOI: https://doi.org/10.1006/eujc.1997.0191
Tiivistelmä
For a finite undirected graph G = (V, E) and a subset A subset of or equal to V, the vertex switching of G by A is defined as the graph G(A) = (V, E'), which is obtained from;by removing all edges between A and its complement (A) over bar and adding as edges all nonedges between A and (A) over bar. The switching class [G] determined by G consists of all vertex switchings G(A) for subsets A subset of or equal to V. We prove that the trees of a switching class [G] are isomorphic to each other. We also determine the types of trees T that have isomorphic copies in [G]. Finally we show that apart from one exceptional type of forest, the real forests in a switching class are isomorphic. Here a forest is real, if it is disconnected. (C) 1998 Academic Press Limited.
For a finite undirected graph G = (V, E) and a subset A subset of or equal to V, the vertex switching of G by A is defined as the graph G(A) = (V, E'), which is obtained from;by removing all edges between A and its complement (A) over bar and adding as edges all nonedges between A and (A) over bar. The switching class [G] determined by G consists of all vertex switchings G(A) for subsets A subset of or equal to V. We prove that the trees of a switching class [G] are isomorphic to each other. We also determine the types of trees T that have isomorphic copies in [G]. Finally we show that apart from one exceptional type of forest, the real forests in a switching class are isomorphic. Here a forest is real, if it is disconnected. (C) 1998 Academic Press Limited.
Turun yliopiston Tutkimustietojärjestelmän portaali