The realization graph of a degree sequence with majorization gap 1 is Hamiltonian (Q1300907)

All graphs \(G=(V,E)\) considered in the present paper are finite and simple. A sequence \(d=(d_1,d_2, \dots, d_n)\) is called a degree sequence if there exists a graph \(G\) on \(V=\{1,2, \dots, n\}\) such that \(\deg (i)=d_i\) for all \(i\), and \(G\) is said to be a realization of \(d\) of the length \(n\). The realization graph \({\mathfrak G}(d)\) of \(d\) is a connected graph which has as vertices the realizations of \(d\), the so-called super vertices. Two super vertices are adjacent in \({\mathfrak G}(d)\) if one can be obtained from the other by deleting two existing edges \([a,b]\), \([c,e]\) and adding two new edges \([a,e]\), \([b,c]\) for some distinct vertices \(a, b c, e\). (This operation is called a cycle exchange.) A graph \(G\) is called a threshold graph if there exist non-negative real vertex-weights such that a set of vertices of \(G\) is independent iff its total weight does not exceed 1 (its degree sequence is then called a threshold sequence). It is known that every degree sequence \(d\) can be transformed into a threshold sequence by repeated operations consisting of subtracting 1 from a degree and adding 1 to a larger or equal degree. The minimum number of these operations required to transform \(d\) into a threshold sequence is called the majorization gap \(R(d)\) of \(d\). Applying these concepts the authors get the following main result: If \(d\) is a degree sequence satisfying \(R(d)=1\), then \({\mathfrak G}(d)\) is Hamiltonian (Theorem 1). In Chapter 2 degree sequences are characterized more detailed by partly known theorems and lemmas and there are given some properties that are used for the extensive induction proof of Theorem 1. Chapter 3 contains a somewhat stronger version of Theorem 1 (Theorem 7).