Acyclicity of switching classes
: Hage J, Harju T
Publisher: ACADEMIC PRESS LTD
: 1998
: European Journal of Combinatorics
: EUROPEAN JOURNAL OF COMBINATORICS
: EUR J COMBIN
: 19
: 3
: 321
: 327
: 7
: 0195-6698
DOI: https://doi.org/10.1006/eujc.1997.0191
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.