Threshold Digraphs

J Res Natl Inst Stand Technol. 2014 May 20:119:227-34. doi: 10.6028/jres.119.007. eCollection 2014.

Abstract

A digraph whose degree sequence has a unique vertex labeled realization is called threshold. In this paper we present several characterizations of threshold digraphs and their degree sequences, and show these characterizations to be equivalent. Using this result, we obtain a new, short proof of the Fulkerson-Chen theorem on degree sequences of general digraphs.

Keywords: Fulkerson-Chen theorem; digraph realizations; threshold digraphs.