On fractional realizations of graph degree sequences

zbMATH Open1300.05266arXiv1310.1112MaRDI QIDQ405210FDOQ405210

Authors: Michael D. Barrus 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We introduce fractional realizations of a graph degree sequence and a closely associated convex polytope. Simple graph realizations correspond to a subset of the vertices of this polytope. We describe properties of the polytope vertices and characterize degree sequences for which each polytope vertex corresponds to a simple graph realization. These include the degree sequences of pseudo-split graphs, and we characterize their realizations both in terms of forbidden subgraphs and graph structure.

Full work available at URL: https://arxiv.org/abs/1310.1112

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The polytope of degree sequences
• On realization graphs of degree sequences
• Adjacency relationships forced by a degree sequence
• scientific article; zbMATH DE number 3885960
• Forcibly bipartite and acyclic (uni-)graphic sequences

zbMATH Keywords

fractional graph theorydegree sequences0/1-polytopes

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex degrees (05C07) Fractional graph theory, fuzzy graph theory (05C72)

Cites Work

• Properties of vertex packing and independence system polyhedra
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Title not available (Why is that?)
• Linear recognition of pseudo-split graphs
• Decomposition of graphical sequences and unigraphs
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• A remark on the existence of finite graphs
• Rao's degree sequence conjecture
• Integer Programming: Methods, Uses, Computations
• Some Properties of Graphs with Multiple Edges
• The splittance of a graph
• Hereditary unigraphs and Erdős-Gallai equalities
• Title not available (Why is that?)
• The polytope of degree sequences
• Title not available (Why is that?)
• Adjacency relationships forced by a degree sequence
• Fractional matroid matchings
• Fractional perfect \(b\)-matching polytopes. I: General theory
• Establishing the matching polytope
• Degree-based graph construction
• On the extreme points of a certain convex polytope
• Title not available (Why is that?)

Cited In (4)

• On realization graphs of degree sequences
• Split graphs and Nordhaus-Gaddum graphs
• The principal Erdős-Gallai differences of a degree sequence
• The polytope of degree sequences

This page was built for publication: On fractional realizations of graph degree sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405210)