Connectedness of the Realization Graph of 4-Regular Graphs with Minimum Decycling Number

Xin Lin
Department of Mathematics, Fuzhou University, Fuzhou 350002, P. R. China

Abstract     Full Text  PDF

Let $\mathcal{R}\left(4^{n}; \displaystyle{\left\lceil \frac{n+1}{3} \right\rceil}\right)$ be the set of all 4-regular graphs with order $n$ whose decycling number is $\displaystyle{\left\lceil \frac{n+1}{3} \right\rceil}$. For any graph $G$ and independent edges $ab, cd$ in $G$ with $ac, bd\notin E(G)$, let $G^{\sigma(a,b;c,d)}=G-\{ab,cd\}+\{ac,bd\}$. Then the operation $\sigma(a,b;c,d)$ is called a switching operation. In this paper, it will be proved that the realization graph of 4-regular graphs with $\phi=\displaystyle{\left\lceil \frac{n+1}{3} \right\rceil}$ is connected under the switching operation.