PPubMed26 Sep 2018Cited 2×

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

Brian Cloteaux

Abstract

We give a sufficient condition for a nonnegative integer list to be graphic based on its largest and smallest elements, length, and sum. This bound generalizes a result of Zverovich and Zverovich.

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Answer

A new inequality using the largest and smallest degrees, sequence length, and sum provides a sharp sufficient condition for a degree sequence to be graphic, reducing the need for full Erdős‑Gallai checks.

What’s new

i.Derives a sharp sufficient inequality (¼((α1+αn+1))^2‑nαn≤0) for graphic sequences based on largest/smallest entries, length, and sum
ii.Shows the bound is tight by constructing sequences that become non‑graphic when any parameter is altered
iii.Compares the new bound with the Zverovich‑Zverovich result, highlighting the necessity of α1≤n‑1
iv.Identifies limitations for regular sequences and provides a workaround using Lemma 1
v.Demonstrates practical use by coupling the condition with Erdős‑Gallai testing to save computation

How they did it

The authors rearrange known inequalities to obtain a new bound, prove its sharpness by constructing counterexample sequences when the bound fails, and compare it analytically to existing results such as Zverovich‑Zverovich and Lemma 1. They also discuss integration with Erdős‑Gallai testing after sorting the degree sequence.

What they found

If ¼((α1+αn+1))^2‑nαn≤0 then the sequence is guaranteed graphic
The bound is sharp: any change violating the inequality yields non‑graphic examples
Requires α1≤n‑1; cannot be relaxed without losing guarantee
Not applicable to regular sequences (α1=αn) but can be handled via Lemma 1
When used before Erdős‑Gallai, it can eliminate the need for full inequality checks for many sequences

Caveats

✕Does not apply to regular (all‑equal) degree sequences
✕Requires the largest degree to satisfy α1≤n‑1, limiting some cases
✕Still needs sorting of the sequence before the condition can be applied
✕May not replace Erdős‑Gallai checks for sequences that fail the inequality

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

Similar papers in all four archives

The same idea searched in arXiv, PubMed, bioRxiv and chemRxiv at once, so a method can lead you to where it is being applied.

AarXiv4 found

Searching the other archives…