$\textbf{Definition:}$ $G$ is a threshold graph if and only if $G$ can be constructed from the one-vertex graph by repeatedly adding an isolated vertex or a dominating vertex.

I am trying to prove the following problem:

Let $d$ = $\{d_1 \geq \cdots \geq d_n \}$ be a degree sequence and define, $r_i = \max\{j : d_j \geq i\}$ and $f = \max\{j : d_j \geq j\}$. Prove that $d$ is a degree sequence of a threshold graph if and only if $r_i = d_i + 1$ for $i=1,\ldots,f$.

I think the overall idea would be to show that if $r_i$ is as claimed, then $d$ must be a degree sequence of a threshold graph because the pattern represents the recursive construction of a threshold graph. And then prove the converse.

I would appreciate some help. Thank you.

  • $\begingroup$ I guess you should change defenition of $f$ to this one: $f = \max(\{\,0\,\} \cup \{\,j \mid d_j \ge j\,\}$ to have correctly defined $f$ for an empty graph (i. e. when all vertex degrees are zero). Also $r_i$ should be defined for $i = 1, \ldots, f$ only. $\endgroup$ – Smylic May 6 '18 at 20:14

One approach would be a careful induction proof. A threshold graph has a recursive structure: it's a smaller threshold graph, with either a dominating vertex or an isolated vertex added on. So you can try to prove that:

  1. One of the following holds:
    • The vertex with degree $d_1$ is a dominating vertex, or
    • The vertex with degree $d_n$ is an isolated vertex.
  2. If you delete the vertex found in step 1, then the degree sequence of the remaining graph continues to satisfy the condition in the problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.