A graph based on sums in a sequence of numbers

Question

Let $x_1,\ldots,x_n$ be numbers such that $1\geq x_1 \geq \cdots \geq x_n\geq 0$.

Construct a undirected graph in which the vertices are $x_1,\ldots,x_n$, and there is an edge between $x_i$ and $x_j$ iff $x_i+x_j\leq 1$.

This graph has a special structure: if it has an edge $(x_i,x_j)$, then it must have the edges $(x_{i'},x_{j'})$ for all $i'\geq i$ and $j'\geq j$.

Is there a term for this class of graphs?

I need the term in order to search for conditions for existence of perfect matchings in such graphs. So if you know of such conditions, this will be great too.

Answer 1

Check out Threshold Graphs The first alternative definition is basically the one you gave. There is a lot of stuff out there about threshold graphs

Answer 2

Since you ask for perfect matchings, we should only consider when $n$ is even. I claim that a necessary and sufficient condition for the existence of a perfect matching is that $x_i + x_{n+1-i} \leq 1$ for all $i \in [n]$.

The condition is clearly sufficient, so we focus on necessity. Suppose there exists $i \leq n/2$ such that $x_i + x_{n+1-i} > 1$. Then the neighbors of each of $x_1, \dots, x_i$ are contained in $\{x_n, \dots, x_{n+2-i}\}$. This is a set of size $i$ whose neighborhood has size $i-1$, so there can be no perfect matching.

One should also be able to give a formula for what is the size of the largest matching.