Title of article
Realizing degree imbalances in directed graphs
Author/Authors
Felix Lazebnik and Dhruv Mubayi، نويسنده , , Todd G. Will، نويسنده , , Douglas B. West، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2001
Pages
7
From page
147
To page
153
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.
Keywords
Directed graph , Feasible flow , Havel–Hakimi Theorem , Degree sequence , Aigner–Triesch method
Journal title
Discrete Mathematics
Serial Year
2001
Journal title
Discrete Mathematics
Record number
949792
Link To Document