On fractional realizations of graph degree sequences

MaRDI QIDQ405210zbMATH OpenFDO

Authors Michael D. Barrus

Publication date 4 September 2014

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

Full work available at URL https://arxiv.org/abs/1310.1112, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p18

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

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)

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.

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

Cites work

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

Cited in

(4)

• The principal Erdős-Gallai differences of a degree sequence
• On realization graphs of degree sequences
• Split graphs and Nordhaus-Gaddum graphs
• 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)