Return to Answer

This is too long for a comment, but it's really just a modification of John Tuwim's answer. By using the reductions discussed in the original post, the proof becomes even simpler and it shows that $$\mathcal{I}_k(G)\leq \mathrm{sp}(G,k-1)(n-\mathrm{sp}(G,k-1))\leq (k+1)(n-k-1).$$

Let $G$ be a graph on $n$ vertices, let $\lceil n/2\rceil\leq k\leq n-1$, let $A=\{v\in V(G): d(v)\geq k\}$, $B=\{v\in V(G):d(v)\leq n-k-1\}$, and $R=V(G)\setminus (A\cup B)$. As mentioned in the original post, we can assume $A$ is clique, $B$ is an independent set, $R=\emptyset$, and $n-k\leq b:=|B|\leq |A|=:a\leq k$ (we can assume $b\leq a$ since $\mathcal{I}_k(G)=\mathcal{I}_k(\bar{G})$).

Now using the result of Erdős et al., there exists $S\subseteq V(G)$ such that $|S|\geq k+1$ and for all $u,v\in S$, $|d(u)-d(v)|\leq k-1$. Let $|s_A|=|S\cap A|$ and $s_B=|S\cap B|$ and note that $$ s_A+s_B=|S|\geq k+1>a\geq b.\tag1 $$ Thus \begin{align*} \mathcal{I}_k(G)&\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)(b-s_B)\\ &\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)s_A+(b-s_B)s_B\\ &=(s_A+s_B)(n-s_A-s_B)\\ &\leq (k+1)(n-k-1) \end{align*} where we used ($1$) in the second and last inequality (in the last inequality we also used the fact that $k+1>n/2$).

Note that this calculation gives an upper bound in terms of $\mathrm{sp}(G, k-1)=s_A+s_B$ and shows that even when $\mathrm{sp}(G, k-1)=s_A+s_B=k+1$ we have a strict inequality provided $s_A<a$ and $s_B<b$.

This is too long for a comment, but it's really just a modification of John Tuwim's answer. By using the reductions discussed in the original post, the proof becomes even simpler and it shows that $$\mathcal{I}_k(G)\leq \mathrm{sp}(G,k-1)(n-\mathrm{sp}(G,k-1))\leq (k+1)(n-k-1).$$

Let $G$ be a graph on $n$ vertices, let $\lceil n/2\rceil\leq k\leq n-1$, let $A=\{v\in V(G): d(v)\geq k\}$, $B=\{v\in V(G):d(v)\leq n-k-1\}$, and $R=V(G)\setminus (A\cup B)$. As mentioned in the original post, we can assume $A$ is clique, $B$ is an independent set, $R=\emptyset$, and $$n-\mathrm{sp}(G,k-1)< b:=|B|\leq |A|=:a<\mathrm{sp}(G,k-1)$$ (we can assume $b\leq a$ since $\mathcal{I}_k(G)=\mathcal{I}_k(\bar{G})$).

Now using the result of Erdős et al., there exists $S\subseteq V(G)$ such that $\mathrm{sp}(G,k-1)=|S|\geq k+1$ and for all $u,v\in S$, $|d(u)-d(v)|\leq k-1$. Let $|s_A|=|S\cap A|$ and $s_B=|S\cap B|$ and note that $$ s_A+s_B=\mathrm{sp}(G,k-1)>a\geq b.\tag1 $$ Thus \begin{align*} \mathcal{I}_k(G)&\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)(b-s_B)\\ &\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)s_A+(b-s_B)s_B\\ &=(s_A+s_B)(n-s_A-s_B)\\ &\leq (k+1)(n-k-1) \end{align*} where we used ($1$) in the second inequality and $\mathrm{sp}(G,k-1)\geq k+1>n/2$ in the last inequality.

Note that this calculation gives an upper bound in terms of $\mathrm{sp}(G, k-1)=s_A+s_B$ and shows that even when $\mathrm{sp}(G, k-1)=s_A+s_B=k+1$ we have a strict inequality provided $s_A<a$ and $s_B<b$.

This is too long for a comment, but it's really just a modification of John Tuwim's answer. By using the reductions discussed in the original post the proof becomes even simpler and it shows that $$\mathcal{I}_k(G)\leq \mathrm{sp}(G,k-1)(n-\mathrm{sp}(G,k-1))\leq (k+1)(n-k-1).$$

Let $G$ be a graph on $n$ vertices, let $\lceil n/2\rceil\leq k\leq n-1$, let $A=\{v\in V(G): d(v)\geq k\}$, $B=\{v\in V(G):d(v)\leq n-k-1\}$, and $R=V(G)\setminus (A\cup B)$. As mentioned in the original post, we can assume $A$ is clique, $B$ is an independent set, $R=\emptyset$, and $n-k\leq b:=|B|\leq |A|=:a\leq k$ (we can assume $b\leq a$ since $\mathcal{I}_k(G)=\mathcal{I}_k(\bar{G})$).

Now using the result of Erdős et al., there exists $S\subseteq V(G)$ such that $|S|\geq k+1$ and for all $u,v\in S$, $|d(u)-d(v)|\leq k-1$. Let $|s_A|=|S\cap A|$ and $s_B=|S\cap B|$ and note that $$ s_A+s_B=|S|\geq k+1>a\geq b.\tag1 $$ Thus \begin{align*} \mathcal{I}_k(G)&\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)(b-s_B)\\ &\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)s_A+(b-s_B)s_B\\ &=(s_A+s_B)(n-s_A-s_B)\\ &\leq (k+1)(n-k-1) \end{align*} where we used ($1$) in the second and last inequality (in the last inequality we also used the fact that $k+1>n/2$).

Note that this calculation gives an upper bound in terms of $\mathrm{sp}(G, k-1)=s_A+s_B$ and shows that even when $\mathrm{sp}(G, k-1)=s_A+s_B=k+1$ we have a strict inequality provided $s_A<a$ and $s_B<b$.

This is too long for a comment, but it's really just a modification of John Tuwim's answer. By using the reductions discussed in the original post, the proof becomes even simpler and it shows that $$\mathcal{I}_k(G)\leq \mathrm{sp}(G,k-1)(n-\mathrm{sp}(G,k-1))\leq (k+1)(n-k-1).$$

Let $G$ be a graph on $n$ vertices, let $\lceil n/2\rceil\leq k\leq n-1$, let $A=\{v\in V(G): d(v)\geq k\}$, $B=\{v\in V(G):d(v)\leq n-k-1\}$, and $R=V(G)\setminus (A\cup B)$. As mentioned in the original post, we can assume $A$ is clique, $B$ is an independent set, $R=\emptyset$, and $n-k\leq b:=|B|\leq |A|=:a\leq k$ (we can assume $b\leq a$ since $\mathcal{I}_k(G)=\mathcal{I}_k(\bar{G})$).

Now using the result of Erdős et al., there exists $S\subseteq V(G)$ such that $|S|\geq k+1$ and for all $u,v\in S$, $|d(u)-d(v)|\leq k-1$. Let $|s_A|=|S\cap A|$ and $s_B=|S\cap B|$ and note that $$ s_A+s_B=|S|\geq k+1>a\geq b.\tag1 $$ Thus \begin{align*} \mathcal{I}_k(G)&\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)(b-s_B)\\ &\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)s_A+(b-s_B)s_B\\ &=(s_A+s_B)(n-s_A-s_B)\\ &\leq (k+1)(n-k-1) \end{align*} where we used ($1$) in the second and last inequality (in the last inequality we also used the fact that $k+1>n/2$).

Note that this calculation gives an upper bound in terms of $\mathrm{sp}(G, k-1)=s_A+s_B$ and shows that even when $\mathrm{sp}(G, k-1)=s_A+s_B=k+1$ we have a strict inequality provided $s_A<a$ and $s_B<b$.

This is too long for a comment, but it's really just a modification of John Tuwim's answer. The only point of this is that by using the reductions discussed in the original post, the proof becomes even simpler.

Let $G$ be a graph on $n$ vertices, let $\lceil n/2\rceil\leq k\leq n-1$, let $A=\{v\in V(G): d(v)\geq k\}$, $B=\{v\in V(G):d(v)\leq n-k-1\}$, and $R=V(G)\setminus (A\cup B)$. As mentioned in the original post, we can assume $A$ is clique, $B$ is an independent set, $R=\emptyset$, and $n-k\leq b:=|B|\leq |A|=:a\leq k$ (we can assume $b\leq a$ since $\mathcal{I}_k(G)=\mathcal{I}_k(\bar{G})$).

Now using the result of Erdős et al., there exists $S\subseteq V(G)$ such that $|S|\geq k+1$ and for all $u,v\in S$, $|d(u)-d(v)|\leq k-1$. Let $|s_A|=|S\cap A|$ and $s_B=|S\cap B|$ and note that $$ s_A+s_B=|S|\geq k+1>a\geq b.\tag1 $$ Thus \begin{align*} \mathcal{I}_k(G)&\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)(b-s_B)\\ &\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)s_A+(b-s_B)s_B\\ &=(s_A+s_B)(n-s_A-s_B)\\ &\leq (k+1)(n-k-1) \end{align*} where we used ($1$) in the second and last inequality (in the last inequality we also used the fact that $k+1>n/2$).

Note that this calculation gives an upper bound in terms of $sp(G, k-1)=s_A+s_B$ and shows that even when $sp(G, k-1)=s_A+s_B=k+1$ we have a strict inequality provided $s_A<a$ and $s_B<b$.

This is too long for a comment, but it's really just a modification of John Tuwim's answer. By using the reductions discussed in the original post the proof becomes even simpler and it shows that $$\mathcal{I}_k(G)\leq \mathrm{sp}(G,k-1)(n-\mathrm{sp}(G,k-1))\leq (k+1)(n-k-1).$$

Let $G$ be a graph on $n$ vertices, let $\lceil n/2\rceil\leq k\leq n-1$, let $A=\{v\in V(G): d(v)\geq k\}$, $B=\{v\in V(G):d(v)\leq n-k-1\}$, and $R=V(G)\setminus (A\cup B)$. As mentioned in the original post, we can assume $A$ is clique, $B$ is an independent set, $R=\emptyset$, and $n-k\leq b:=|B|\leq |A|=:a\leq k$ (we can assume $b\leq a$ since $\mathcal{I}_k(G)=\mathcal{I}_k(\bar{G})$).

Now using the result of Erdős et al., there exists $S\subseteq V(G)$ such that $|S|\geq k+1$ and for all $u,v\in S$, $|d(u)-d(v)|\leq k-1$. Let $|s_A|=|S\cap A|$ and $s_B=|S\cap B|$ and note that $$ s_A+s_B=|S|\geq k+1>a\geq b.\tag1 $$ Thus \begin{align*} \mathcal{I}_k(G)&\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)(b-s_B)\\ &\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)s_A+(b-s_B)s_B\\ &=(s_A+s_B)(n-s_A-s_B)\\ &\leq (k+1)(n-k-1) \end{align*} where we used ($1$) in the second and last inequality (in the last inequality we also used the fact that $k+1>n/2$).

Note that this calculation gives an upper bound in terms of $\mathrm{sp}(G, k-1)=s_A+s_B$ and shows that even when $\mathrm{sp}(G, k-1)=s_A+s_B=k+1$ we have a strict inequality provided $s_A<a$ and $s_B<b$.