Mathematics – Combinatorics
Scientific paper
2011-12-06
Mathematics
Combinatorics
7 pages, 1 figure
Scientific paper
We consider the following fundamental realization problem of directed graphs. Given a sequence $S:={a_1 \choose b_1},...,{a_n \choose b_n}$ with $a_i,b_i\in \mathbb{Z}_0^+.$ Does there exist a digraph (no parallel arcs allowed) $G=(V,A)$ with a labeled vertex set $V:=\{v_1,...,v_n\}$ such that for all $v_i \in V$ indegree and outdegree of $v_i$ match exactly the given numbers $a_i$ and $b_i$, respectively? There exist two known approaches solving this problem in polynomial running time. One first approach of Kleitman and Wang (1973) uses recursive algorithms to construct digraph realizations. The second one draws back into the Fifties and Sixties of the last century and gives a complete characterization of digraph sequences (Gale 1957, Fulkerson 1960, Ryser 1957, Chen 1966). That is, one has only to validate a certain number of inequalities. Chen bounded this number by $n$. His characterization demands the property that $S$ has to be in lexicographical order. We show that this condition is much too strong. Hence, we can give several, different sets of $n$ inequalities. We think that this stronger result can be very important with respect to structural insights about the sets of digraph sequences for example in the context of threshold sequences. The new characterization is fomally analogous to the classical one by Erd\"os and Gallai (1960) for undirected graphs.
No associations
LandOfFree
A Note on the Characterization of Digraph Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Note on the Characterization of Digraph Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on the Characterization of Digraph Sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-380827