Affordable Access

Publisher Website

Realizing degree imbalances in directed graphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
239
Identifiers
DOI: 10.1016/s0012-365x(01)00048-6
Keywords
  • Directed Graph
  • Degree Sequence
  • Havel–Hakimi Theorem
  • Aigner–Triesch Method
Disciplines
  • Computer Science

Abstract

Abstract In a directed graph, the imbalance of a vertex v is b(v)=d +(v)−d −(v) . We characterize the integer lists that can occur as the sequence of imbalances of a simple directed graph. For the realizable sequences, we determine the maximum number of arcs in a realization and provide a greedy algorithm that constructs realizations with the minimum number of arcs.

There are no comments yet on this publication. Be the first to share your thoughts.