Contributions to the theory of graphic sequences

Zverovich, I. E.; Zverovich, V. E.; Zverovich, Igor; Zverovich, Vadim

Abstract

In this article we present a new version of the Erdős-Gallai theorem concerning graphicness of the degree sequences. The best conditions of all known on the reduction of the number of Erdős-Gallai inequalities are given. Moreover, we prove a criterion of the bipartite graphicness and give a sufficient condition for a sequence to be graphic which does not require checking of any Erdős-Gallai inequality. © 1992.

• Journal Article Type: Article
• Publication Date: Aug 14, 1992
• Journal: Discrete Mathematics
• Print ISSN: 0012-365X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 105
• Issue: 1-3
• Pages: 293-303
• DOI: https://doi.org/10.1016/0012-365X%2892%2990152-6
• Keywords: graphic sequences
• Public URL: https://uwe-repository.worktribe.com/output/1109788
• Publisher URL: http://dx.doi.org/10.1016/0012-365X(92)90152-6