2-Vertex Self Switching of Trees - Jayasekaran, C.; Sudha, J. Christabel; Shijo, M. Ashwin (Communications in Mathematics and Applications, 2022)
For a finite undirected graph \(G(V,E)\) and a non empty subset \(σ V\), the switching of \(G\) by \(σ\) is defined as the graph \(G^σ (V, E’)\) which is obtained from \(G\) by removing all edges between \(σ\) and its complement \(V\)-\(σ\) and adding as edges all non-edges between \(σ\) and \(V\)-\(σ\). For \(σ={v}\), we write \(G^v\) instead of \(G^{v \) and the corresponding switching is called as vertex switching. We also call it as \(|σ|\)-vertex switching. When \(|σ|=2\), it is termed as 2-vertex switching. If \(G G^σ\), then it is called self vertex switching. A subgraph \(B\) of \(G\) which contains \(G[σ]\) is called a joint at \(σ\) in \(G\) if \(B-σ\) is connected and maximal. If \(B\) is connected, then we call \(B\) as a \(c\)-joint and otherwise a \(d\)-joint. A graph with no cycles is called an acyclic graph. A connected acyclic graph is called a tree. In this paper, we give necessary and sufficient conditions for a graph \(G\), for which \(G^σ\) at \(σ ={u, v}\) to be connected and acyclic when \(uvE(G)\) and \(uv otin E(G)\). Using this, we characterize trees with a 2-vertex self switching.