Some Results on 2-Vertex Switching in Joints

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')\) 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\), we call it as 2-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 \(c\)-joint otherwise \(d\)-joint. In this paper, we give a necessary and sufficient condition for a \(c\)-joint \(B\) at \(\sigma = \{u,v\}\) in \(G\) to be a \(c\)-joint and a \(d\)-joint at \(\sigma\) in \(G^{\sigma}\) and also a necessary and sufficient condition for a \(d\)-joint \(B\) at \(\sigma = \{u,v\}\) in \(G\) to be a \(c\)-joint and a \(d\)-joint at \(\sigma\) in \(G^{\sigma}\) when \(uv\in E(G)\) and when \(uv\notin E(G)\).