A1 Refereed original research article in a scientific journal
Acyclicity of switching classes
Authors: Hage J, Harju T
Publisher: ACADEMIC PRESS LTD
Publication year: 1998
Journal:: European Journal of Combinatorics
Journal name in source: EUROPEAN JOURNAL OF COMBINATORICS
Journal acronym: EUR J COMBIN
Volume: 19
Issue: 3
First page : 321
Last page: 327
Number of pages: 7
ISSN: 0195-6698
DOI: https://doi.org/10.1006/eujc.1997.0191
Abstract
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.
UTU Research Portal