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

DOI10.1016/S0024-3795(98)10229-XzbMath0932.05023MaRDI QIDQ1300907

Uri N. Peled, Srinivasa R. Arikati

Publication date: 13 March 2000

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

degree sequencethreshold graphrealization graphthreshold sequencecycle exchangeHamilton graphmajorization gap

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Eulerian and Hamiltonian graphs (05C45) Vertex degrees (05C07) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

Split graphs ⋮ On realization graphs of degree sequences ⋮ Cliques in realization graphs ⋮ Upward-closed hereditary families in the dominance order

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The polytope of degree sequences
• Matrices of zeros and ones with fixed row and column sum vectors
• The splittance of a graph
• Degree sequences and majorization
• Parallel concepts in graph theory
• Hamiltonicity of a type of interchange graphs
• Threshold graphs and related topics
• Matroid basis graphs. I
• Matroid basis graphs. II
• Extreme degree sequences of simple graphs
• On a conjecture of wang and williams
• Threshold Sequences
• The threshold weight of a graph
• Some Properties of Graphs with Multiple Edges
• Inequalities: theory of majorization and its applications

This page was built for publication: The realization graph of a degree sequence with majorization gap 1 is Hamiltonian