Realizing degree imbalances in directed graphs (Q5946755): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Importer (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: math/9807043 / rank
 
Normal rank

Latest revision as of 11:28, 18 April 2024

scientific article; zbMATH DE number 1659502
Language Label Description Also known as
English
Realizing degree imbalances in directed graphs
scientific article; zbMATH DE number 1659502

    Statements

    Realizing degree imbalances in directed graphs (English)
    0 references
    0 references
    0 references
    0 references
    29 March 2002
    0 references
    In a digraph, the imbalance of a vertex \(v\) with out-degree \(d^+(v)\) and in-degree \(d^-(v)\) is \(d^+(v)-d^-(v)\). The imbalance sequences of digraphs are characterized (an analogy of the Havel-Hakimi theorem is given). Besides an algorithmic proof the authors present also two other proofs. For a realizable sequence their greedy algorithm produces a digraph with the fewest arcs. Also the maximum number of arcs is determined for a realization without opposed arcs.
    0 references
    0 references
    digraph
    0 references
    degree sequence
    0 references
    imbalance sequence
    0 references
    Havel-Hakimi theorem
    0 references

    Identifiers