The r-switching-stable graphs

Abstract

Bondy and Mercier (2011) defined a switching at a vertex of a digraph to be the operation of reversing the directions of the edges incident with that vertex. They asked which digraphs have the property that every switching produces a digraph isomorphic to the original, which they called switching-stability. That version of the problem was solved for oriented graphs by the second author and Schweitzer (McKay and Schweitzer, 2014). In this paper we generalise the problem in several directions. As well as oriented graphs, we consider graphs with coloured vertices or edges, and various types of switching which apply to them. We further consider r-switching-stable graphs, which are those for which any r distinct switchings together produce a graph isomorphic to the original. Finally, we consider what happens if the isomorphism relation between graphs is weakened to isomorphism up to converse (reversal of all directed edges or changing of all colours). Our proofs employ a combination of group theory and combinatorics, with a small amount of computer assistance.