The realization graph of a degree sequence with majorization gap 1 is Hamiltonian
type: Item
instance of: scholarly article
title: The realization graph of a degree sequence with majorization gap 1 is Hamiltonian
zbMATH Open document ID: 0932.05023
DOI: 10.1016/S0024-3795(98)10229-X
author: S. R. Arikati
author: Uri N. Peled
published in: Linear Algebra and its Applications
publication date: 2000-03-13T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1331375
zbMATH Keywords: Hamilton graph
zbMATH Keywords: degree sequence
zbMATH Keywords: realization graph
zbMATH Keywords: cycle exchange
zbMATH Keywords: threshold graph
zbMATH Keywords: threshold sequence
zbMATH Keywords: majorization gap
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Degree sequences and majorization
cites work: Q3941433
cites work: Matrices of zeros and ones with fixed row and column sum vectors
cites work: Q4165164
cites work: Some Properties of Graphs with Multiple Edges
cites work: Threshold Sequences
cites work: Parallel concepts in graph theory
cites work: Q5812325
cites work: The splittance of a graph
cites work: Extreme degree sequences of simple graphs
cites work: Hamiltonicity of a type of interchange graphs
cites work: On a conjecture of wang and williams
cites work: Threshold graphs and related topics
cites work: Inequalities: theory of majorization and its applications
cites work: Matroid basis graphs. I
cites work: Matroid basis graphs. II
cites work: Q4294622
cites work: The polytope of degree sequences
cites work: Q3910567
cites work: The threshold weight of a graph
description: scientific article; zbMATH DE number 1331375