Some criteria for integer sequences pair being realizable by a graph

Abstract

Let $A=(a_1,\dots ,a_n)$ and $B=(b_1,\dots ,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,\dots ,v_n$ such that $a_i\le d_G(v_i)\le b_i$ for $1\le i\le n$. Let $⪯$ denote the lexicographic ordering on $Z\times Z:$ $(a_{i+1},b_{i+1})⪯(a_i,b_i)⟺[(a_{i+1}<a_i)\vee ((a_{i+1}=a_i)\&(b_{i+1}\le b_i))]$. We say that the sequences $A$ and $B$ are in good order if $(a_{i+1},b_{i+1})⪯(a_i,b_i)$. In this paper, we consider the generalizations of six classical characterizations on sequences pair due to Berge, Ryser et al. and present related results.