2-Vertex Self Switching of Trees

Abstract

For a finite undirected graph $G(V,E)$ and a non empty subset $\sigma \subseteq V$, the switching of $G$ by $\sigma$ is defined as the graph $G^{\sigma }(V,E^{\prime })$ which is obtained from $G$ by removing all edges between $\sigma$ and its complement $V$-$\sigma$ and adding as edges all non-edges between $\sigma$ and $V$-$\sigma$. For $\sigma =\{v\}$, we write $G^v$ instead of $G^{\{v\}}$ and the corresponding switching is called as vertex switching. We also call it as $|\sigma |$-vertex switching. When $|\sigma |=2$, it is termed as 2-vertex switching. If $G\cong G^{\sigma }$, then it is called self vertex switching. A subgraph $B$ of $G$ which contains $G[\sigma ]$ is called a joint at $\sigma$ in $G$ if $B-\sigma$ 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^{\sigma }$ at $\sigma =\{u,v\}$ to be connected and acyclic when $uv\in E(G)$ and $uv\notin E(G)$. Using this, we characterize trees with a 2-vertex self switching.