The realization graph of a degree sequence with majorization gap 1 is Hamiltonian
| Autor: | Uri N. Peled, Srinivasa R. Arikati |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Discrete mathematics
Numerical Analysis Algebra and Number Theory Degree (graph theory) Quartic graph Hamiltonian path Vertex (geometry) Combinatorics symbols.namesake Degree sequence Realization Frequency partition of a graph Hamiltonian graph symbols Discrete Mathematics and Combinatorics Path graph Regular graph Majorization Geometry and Topology Mathematics |
| Zdroj: | Linear Algebra and its Applications. 290:213-235 |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/s0024-3795(98)10229-x |
| Popis: | 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 d i . 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect