The realization graph of a degree sequence with majorization gap 1 is Hamiltonian |
| |
Authors: | Srinivasa R. Arikati Uri N. Peled |
| |
Affiliation: | aCadence Design Systems, Mail Stop 2B1, 555 River Oaks Prkwy, San Jose, CA 95134, USA bMathematics, Statistics, and Computer Science Department, University of Illinois at Chicago, 851 S. Morgan (MIC 249), Chicago, IL 60607-7045, USA |
| |
Abstract: | It is known that the degree sequences of threshold graphs are characterized by the property that they are not majorized strictly by any degree sequence. Consequently every degree sequence d can be transformed into a threshold sequence by repeated operations consisting of subtracting I 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 of d. A realization of a degree sequence d of length n is a graph on the vertices 1, …, n, where the degree of vertex i is di. The realization graph %plane1D;4A2;(d) of a degree sequence d has as vertices the realizations of d, and two realizations are neighbors in %plane1D;4A2;(d) if one can be obtained from the other by deleting two existing edges [a, b], [c, d] and adding two new edges [a, d]; [b, c] for some distinct vertices a, b, c, d. It is known that %plane1D;4A2;(d) is connected. We show that if d has a majorization gap of 1, then %plane1D;4A2;(d) is Hamiltonian. |
| |
Keywords: | Degree sequence Realization Majorization Hamiltonian graph |
本文献已被 ScienceDirect 等数据库收录! |
|