Constrained Switchings in Cubic Graphs

Abstract

The graph $\mathcal{R}(d)$ of realizations of $d$ is a graph whose vertices are the graphs with degree sequence $d$, two vertices are adjacent in the graph $\mathcal{R}(d)$ if one can be obtained from the other by a switching. It has been shown that the graph $\mathcal{R}(d)$ is connected. Let $\mathcal{C}\mathcal{R}(d)$ be the set of connected graphs with degree sequence $d$. Taylor $[13]$ proved that the subgraph of $\mathcal{R}(d)$ induced by $\mathcal{C}\mathcal{R}(d)$ is connected. Several connected subgraphs of $\mathcal{C}\mathcal{R}(d)(3^n)$ are obtained in this paper. As an application, we are able to obtain the interpolation and extremal results for the number of maximum induced forests in the classes of connected subgraphs of $\mathcal{C}\mathcal{R}(d)(3^n)$.