On the switch-length of two connected graphs with the same degree sequence

Abstract

Let G be a simple graph containing distinct vertices x, y, z, w such that the edges {x, y}, {z, w} ∈ G and {x, z}, {y, w} ∉ G. The process of deleting the edges {x, y}, {z, w} from G and adding {x, z}, {y, w} to G is referred to as a switch (or 2-switch) in G. Let G1 and G2 be two connected simple graphs with the same vertex set V such that for all v ∈ V, the degree of v in G1 is the same as in G2 . It is well known that G2 can be obtained from G1 by a sequence of switches. Moreover, there is one such sequences of switches with only connected graphs. For some classes of graphs, we study the problem of finding bounds for the minimum number of switches required for transforming G1 into G2 such that all graphs in the sequence are connected.