Alternating cycles and realizations of a degree sequence
Zofia Majcher · Czech digital mathematics library · 1987
We find an algorithm for constructing finite sequences of certain graphs (realizations of a degree sequence on a given set) with given initial and final graphs such that each subsequent graph is obtained from the preceding one by a switching.Key words: Graph, realization of a degree sequence.Classification: 05C99 °-Introduction.In this paper, we deal with finite, undirected graphs admitting multiple edges and loops and we also consider some special types of graphs, e.g.graphs without loops, k-graphs, simple graphs.We are interested in the class ^y(d) of all graphs being realizations of a degree sequence d on a given set V. The class IRy(d) is closed under switching operation (see [2]).One of the most important properties of the class iRy(d) is contained in the following Theorem.If G,H eIRy(d), then there exists a sequence (*) G°,G 1 l ...,«f l such that G°=-G, G^H and for every s eto,l,.. .,m-ll the graph G s is obtained from G s by a switching.Several proofs of this theorem were presented in the literature.In those proofs different methods have been used for different types of graphs (see [l3,[3],U],C63), Our aim is to find a method of the proof which is effective, uniform and optimal.In this paper an algorithm for constructing the sequence (*) is given.This algorithm can be applied to all types of graphs mentioned above.It can generate a shortest sequence (*), however, in general, solutions are not optimal.Our method is partially based on ideas contained in 153.Namely, we make use of the fact that the symmetrical difference G~H of two graphs G,He tRy(d) can be decomposed into alternating cycles of some special forms.Therefore, we have to prove several properties of alternating cycles.