A Sufficient Condition for Graphic Sequences with Given Largest and Smallest Entries, Length, and Sum

Area of Science:

• Graph theory
• Discrete mathematics

Background:

• Determining if a sequence of nonnegative integers can be the degree sequence of a simple graph (i.e., is graphic) is a fundamental problem in graph theory.
• Existing criteria, such as the Erdős–Gallai theorem, provide necessary and sufficient conditions, but simpler sufficient conditions are also valuable for specific applications.

Purpose of the Study:

• To develop a new sufficient condition for a list of nonnegative integers to be graphic.
• To generalize and extend existing results in graphic sequence determination.

Main Methods:

• The study focuses on analyzing properties of nonnegative integer lists, specifically their largest and smallest elements, total sum, and length.
• A novel bound is derived and proven to be a sufficient condition for a list to be graphic.

Main Results:

• A new sufficient condition for graphic sequences is presented, which depends on the maximum element, minimum element, length, and sum of the sequence.
• This condition is shown to be a generalization of a previously established bound by Zverovich and Zverovich.

Conclusions:

• The newly derived sufficient condition offers a practical criterion for identifying graphic sequences.
• The generalization of existing results contributes to the ongoing development of graphic sequence theory.