Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Is This for Real?: Fast Graphicality Testing

Published

Author(s)

Brian D. Cloteaux

Abstract

When we have an integer sequence that can be realized as the degree sequence of some graph, we say that the sequence is graphic. While almost any graph theory book describes how a sequence can be tested to see if it’s graphic, surprisingly (because this testing has common applications), very little has been written about how to do it efficiently. This highlights the gap between simply knowing that a problem is theoretically tractable and being able to implement an efficient algorithm for practical use.
Citation
Computing in Science & Engineering
Volume
17
Issue
6

Keywords

graphicality testing, degree sequences

Citation

Cloteaux, B. (2015), Is This for Real?: Fast Graphicality Testing, Computing in Science & Engineering, [online], https://doi.org/10.1109/MCSE.2015.125 (Accessed October 31, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created November 1, 2015, Updated November 10, 2018