Some criteria for integer sequences pair being realizable by a graph

Jiyun Guo, Miao Fu, Jun WangarXiv 2022 · DOI · arXiv

TL;DR

This paper tackles the problem of determining whether a graph can be constructed such that the degrees of its vertices fall within specific target intervals. Building on a known generalization of the Erdös-Gallai theorem, the authors successfully generalize six other classical graph realization criteria (such as those by Berge, Ryser, and Bollobás) to apply to pairs of bounding sequences, expanding the theoretical toolkit for network design and graph generation.

What Problem Does This Paper Address?

In graph theory, a classic problem asks: Given a list of integers, can we draw a graph where the vertices have exactly these degrees? A sequence that allows for such a graph is called "realizable." Over the decades, mathematicians have developed several classical criteria to test for realizability, including the famous Erdös-Gallai, Berge, and Ryser theorems.

However, modern network design often requires flexibility. Instead of exact degrees, we might only know that a vertex's degree must fall within a specific range (an interval). We are given a sequence of lower bounds $A = (a_1, \dots, a_n)$ and upper bounds $B = (b_1, \dots, b_n)$.

Previous work by Cai et al. successfully generalized the Erdös-Gallai criterion to handle these interval pairs (provided the sequences are sorted in a specific lexicographic way, called "good order"). This paper asks the logical follow-up question: Can the remaining six classical criteria for single sequences also be generalized to handle sequence pairs?

Methods

This is a theoretical mathematics paper, so the methodology relies on formal logic, algebraic manipulation, and mathematical induction.

Rather than proving graph realizability from scratch for each new theorem, the authors use a clever shortcut: they prove that their newly proposed criteria are mathematically equivalent to the already-proven generalized Erdös-Gallai criterion (referred to in the paper as the CDZ condition).

To do this, they establish a cycle of logical implications. They show that if a sequence pair satisfies the generalized Fulkerson criterion, it satisfies the generalized Bollobás criterion, which satisfies the generalized Grünbaum criterion, and so on, eventually looping back to the CDZ condition. They also introduce helper lemmas (specifically Lemma 3.1 and 3.2) to algebraically reduce the number of inequalities that need to be checked, streamlining the proofs.

Datasets

Not discussed in the paper. As this is a theoretical combinatorial mathematics paper, no empirical datasets were used for training or evaluation.

Key Insights and Ideas

  • Equivalence holds across the board: The most striking insight is that the deep mathematical symmetries connecting the classical degree sequence theorems remain intact when expanded from exact integers to intervals. If you can bound a degree sequence problem using an Erdös-Gallai style inequality, you can also bound it using Fulkerson or Bollobás style inequalities.
  • The importance of "Good Order": These generalizations do not work on arbitrary lists of intervals. The sequences $A$ (lower bounds) and $B$ (upper bounds) must be in "good order"—meaning they are sorted lexicographically. This ordering is the structural glue that allows the classical proofs to scale to intervals.
  • Algorithmic shortcuts: Through Lemma 3.2, the authors prove that you don't actually need to check the inequalities for all $n$ vertices to guarantee realizability. You only need to check up to a specific index $s$ (the largest integer where $a_s \ge s-1$). This significantly reduces the computational complexity if one were to write an algorithm to check these criteria.

Key Results

  • Four Complete Generalizations: The authors successfully formulated generalized criteria for the Fulkerson, Bollobás, Grünbaum, and Hässelbarth theorems (Theorems 2.4 through 2.7). They proved these new criteria are both necessary and sufficient for an interval pair to be realizable by a graph.
  • Partial Generalizations: For Berge's criterion, they established a necessary condition (Theorem 2.1) and a separate sufficient condition (Theorem 2.2). For Ryser's criterion, they established a necessary condition linking the problem to bipartite interval realizability (Theorem 2.3).
  • Counterexamples: The authors explicitly proved that the exact converses of their Berge and Ryser generalizations are false by providing concrete numerical counterexamples (e.g., $A = (5, 4, 3, 3, 3, 1)$ and $B = (5, 5, 3, 3, 3, 1)$).

Limitations and Future Work

Limitations: * The strict reliance on the "good order" (lexicographic sorting) constraint means these criteria cannot be blindly applied to any arbitrary set of upper and lower bounds. * Furthermore, the generalizations for Berge's and Ryser's criteria are not perfectly "if and only if" (necessary and sufficient) in a single unified theorem, unlike the other four.

Future Work: While not explicitly mapped out by the authors, the obvious next steps for this sub-field would be:

  1. Finding exact necessary and sufficient conditions for the Berge and Ryser interval generalizations.
  2. Translating these mathematical criteria into optimized algorithms to programmatically check for graph realizability in large-scale network design problems.

Summary updated

Abstract

Let $A=(a_1,\ldots,a_n)$ and $B=(b_1,\ldots,b_n)$ be two sequences of nonnegative integers with $a_i \le b_i$ for $1\le i\le n$. The pair $(A;B)$ is said to be realizable by a graph if there exists a simple graph $G$ with vertices $v_1,\ldots, v_n$ such that $a_i\le d_G(v_i)\le b_i$ for $1\le i\le n$. Let $\preceq$ denote the lexicographic ordering on $Z\times Z:$ $(a_{i+1},b_{i+1})\preceq (a_i,b_i)\Longleftrightarrow [(a_{i+1}
BibTeX
@misc{guo2022some,
  author = {Jiyun Guo and Miao Fu and Jun Wang},
  title = {{Some criteria for integer sequences pair being realizable by a graph}},
  year = {2022},
  eprint = {2209.06379},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.06379},
}
Figure