Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2014 May 20:119:227-34.
doi: 10.6028/jres.119.007. eCollection 2014.

Threshold Digraphs

Brian Cloteaux  1 , M Drew LaMar  2 , Elizabeth Moseman  1 , James Shook  1
Affiliations

Threshold Digraphs

Brian Cloteaux et al. J Res Natl Inst Stand Technol. .

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.

PubMed Disclaimer

Figures

Fig. 1
Fig. 1
A 2-switch (left) and an induced directed 3-cycle (right). Solid arcs must appear in the digraph and dashed arcs must not appear in the digraph. If an arc is not listed, then it may or may not be present.
See this image and copyright information in PMC

References

    1. Diestel R. Graph theory, Graduate Texts in Mathematics. 4th ed. Vol. 173. Springer; Heidelberg: 2010.
    1. Rao AR, Jana R, Bandyopadhyay S. A Markov chain Monte Carlo method for generating random (0,1)-matrices with given marginals. Sankhyā Ser A. 1996;58(2):225–242. http://sankhya.isical.ac.in/search/58a2/58a2021.pdf.
    1. Mahadev NVR, Peled UN. Threshold graphs and related topics, Annals of Discrete Mathematics. Vol. 56. North-Holland Publishing Co; Amsterdam: 1995.
    1. Berger A. A note on the characterization of digraph sequences. http://arxiv.org/abs/1112.1215.
    1. Berger A. Ph.D. thesis. Martin-Luther-Universität Halle-Wittenberg; 2011. Directed Degree Sequences.

LinkOut - more resources