Acyclicity of switching classes




Hage J, Harju T

PublisherACADEMIC PRESS LTD

1998

European Journal of Combinatorics

EUROPEAN JOURNAL OF COMBINATORICS

EUR J COMBIN

19

3

321

327

7

0195-6698

DOIhttps://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.



Last updated on 2025-13-10 at 12:36