Acyclicity of switching classes (Q1266389): Difference between revisions

If \(G=(V,E)\) is a finite undirected graph and \(A\subset V\), then the vertex switching of \(G\) by \(A\) is defined as the graph \(G_A=(V,E')\), which is obtained from \(G\) by removing all edges between \(A\) and its complement \(\overline A\) and adding as edges all nonedges between \(A\) and \(\overline A\). Vertex switching defines an equivalence relation on the set of graphs with vertex set \(V\). The switching class \([G]\) determined by \(G\) consists of all vertex switchings \(G_A\) for subsets \(A\subseteq V\). The main result of this paper is that every switching class contains at most one tree up to isomorphism. Trees \(T\) such that \([T]\) contains two isomorphic but unequal trees are completely characterized. Similar results are proved for real (disconnected) forests, however it is possible for a switching class to contain two nonisomorphic real forests, but only if the forest is of a specific type.