A note on the characterization of digraphic sequences

DOI10.1016/J.DISC.2013.09.010zbMATH Open1277.05076arXiv1112.1215OpenAlexW2112021853MaRDI QIDQ383344FDOQ383344

Authors: Annabell Berger 

Publication date: 3 December 2013

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (7)

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

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)