A note on the characterization of digraphic sequences

DOI10.1016/J.DISC.2013.09.010MaRDI QIDQ383344zbMATH OpenOpenAlexFDO

Authors Annabell Berger

Publication date 3 December 2013

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1215

zbMATH Keywords

graphic sequencedegree listdigraph characterizationdigraphic listdigraphic sequencedirected degree sequenceGallaigraph characterizationrealization problemRyser-GaleErdős

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)

Abstract: We consider the following fundamental realization problem of directed graphs. Given a sequence $S:=a_{1}choose{b}_1,dots,a_{n}choose{b}_n$ with $a_i,b_{i}inmathbb{Z}_0^{+}.$ Does there exist a digraph (no loops and no parallel arcs are allowed)$G=(V,A)$ with a labeled vertex set $V:=v_1,dots,v_n$ such that for all $v_{i}inV$ 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 cite{KleitWang:73}. 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 stronger than necessary. We provide a new characterization which is formally analogous to the classical one by Erd{H o}s and Gallai (1960) for graphs. 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. Furthermore, the number of inequalities can be restricted to all $kin1,dots,n-1$ with $a_{k+1}>a_k$ and to $k=n.$ An analogous result for graphs was given by Tripathi and Vijay cite{TripathiVijay03}. We prove this property also for the case of digraphs (no parallel arcs) with at most one loop per vertex.

Recommendations

• scientific article; zbMATH DE number 932617
• Characterization of digraphic sequences with strongly connected realizations
• scientific article; zbMATH DE number 970793
• scientific article; zbMATH DE number 25611
• Dag realizations of directed degree sequences

Cites work

• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• A note on a theorem of Erdős and Gallai
• A remark concerning graphical sequences
• A remark on the existence of finite graphs
• A theorem on flows in networks
• Algorithms for constructing graphs and digraphs with given valences and factors
• Combinatorial Properties of Matrices of Zeros and Ones
• Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• On the realization of a (p,s)-digraph with prescribed degrees
• Zero-one matrices with zero trace

Cited in

(7)

• Leaf realization problem, caterpillar graphs and prefix normal words
• A constructive proof of the Fulkerson-Ryser characterization of digraphic sequences
• Sufficient conditions for graphicality of bidegree sequences
• Graphs with prescribed local neighborhoods of their universal coverings
• Realization problems on reachability sequences
• A Characterization of the extended DII-sequence
• Characterization of digraphic sequences with strongly connected realizations

This page was built for publication: A note on the characterization of digraphic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q383344)