2-Vertex self switching of forest

  • C. Jayasekaran Pioneer Kumaraswamy College Nagercoil-629003, Tamil Nadu, India
  • J. Christabel Sudha Pioneer Kumaraswamy College Nagercoil-629003, Tamil Nadu, India.
  • M. Ashwin Shijo Pioneer Kumaraswamy College, Nagercoil-629003, Tamil Nadu, India

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$, it is termed 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 a $c$-joint and otherwise a $d$-joint. A graph with no cycles is called an acyclic graph. Any graph without cycles is a forest. 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}$ where $\sigma = \{u, v\}$ to be disconnected and acyclic whenu $v\in E(G)$ and $uv\notin E(G)$. Using this, we characterize forests with a 2-vertex self switching.

Published
2021-08-20