In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class $\mathcal{G}$, we are concerned with the maximum subclass and the minimum superclass of $\mathcal{G}$ that are closed under switching. We characterize the maximum subclass for many important classes $\mathcal{G}$, and prove that it is finite when $\mathcal{G}$ is minor-closed and omits at least one graph. For several graph classes, we develop polynomial-time algorithms to recognize the minimum superclass. We also show that the recognition of the superclass is NP-complete for $H$-free graphs when $H$ is a sufficiently long path or cycle, and it cannot be solved in subexponential time assuming the Exponential Time Hypothesis.

A bipartite graph G = ( A , B , E ) is said to be a biconvex bipartite graph if there exist orderings < A in A and < B in B such that the neighbors of every vertex in A are consecutive with respect to < B and the neighbors of every vertex in B are consecutive with respect to < A . A caterpillar is a tree that will result in a path upon deletion of all the leaves. In this paper, we prove that there exists a spanning caterpillar in any connected biconvex bipartite graph . Besides being interesting on its own, this structural result has other consequences. For instance, this directly resolves the burning number conjecture for biconvex bipartite graphs.