% ------------------------------------------------------------------------
% AMS-LaTeX definitions: DAL Thesis ++++ Alex, September 1994 ************
% ------------------------------------------------------------------------
% Thesis Defended on 2002
% ------------------------------------------------------------------------
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.15}{24(2)}{2017}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
%\documentclass[11pt,fullpage]{article} %article
%\setlength{\textwidth}{16 cm}
% \setlength{\oddsidemargin}{0 cm}
% \setlength{\evensidemargin}{2 cm}
%\usepackage[centertags]{amsmath}
\usepackage{amsfonts}
%\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{eepic}
%\usepackage{newlfont}
%\usepackage{algorithm}
%\usepackage{algorithmic}
%\usepackage{xthesis} %DAL Thesis Style
%\usepackage{xtocinc} %Include Table of Contents as the first entry in TOC
%                     Faculty of Grad Studies insists on this!?
%\usepackage[inactive]{srcltx}  %SRC Specials for DVI search
% Fuzz -------------------------------------------------------------------
%\hfuzz2pt % Don't bother to report over-full boxes if over-edge is < 2pt
% Line spacing -----------------------------------------------------------
%\newlength{\defbaselineskip}
%\setlength{\defbaselineskip}{\baselineskip}
%\newcommand{\setlinespacing}[1]%
%           {\setlength{\baselineskip}{#1 \defbaselineskip}}
%\newcommand{\doublespacing}{\setlength{\baselineskip}%
%                           {2.0 \defbaselineskip}}
%\newcommand{\singlespacing}{\setlength{\baselineskip}{\defbaselineskip}}

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newcommand{\BTHM}{\begin{theorem}} \newcommand{\ETHM}{\end{theorem}}
\newtheorem{cor}[theorem]{Corollary}
\newcommand{\BCR}{\begin{cor}} \newcommand{\ECR}{\end{cor}}
\newtheorem{lem}[theorem]{Lemma}
\newcommand{\BL}{\begin{lem}}   \newcommand{\EL}{\end{lem}}
\newtheorem{clm}[theorem]{Claim}
\newcommand{\BCM}{\begin{clm}}   \newcommand{\ECM}{\end{clm}}
\newtheorem{prop}[theorem]{Proposition}
\newcommand{\BP}{\begin{prop}}   \newcommand{\EP}{\end{prop}}
\newtheorem{assm}[theorem]{Assumption}
\newcommand{\BASM}{\begin{assm}}   \newcommand{\EASM}{\end{assm}}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


% MATH -------------------------------------------------------------------
%\newcommand{\A}{{\cal A}}
%\newcommand{\h}{{\cal H}}
%\newcommand{\s}{{\cal S}}
%\newcommand{\W}{{\cal W}}
%\newcommand{\BH}{\mathbf B(\cal H)}
%\newcommand{\KH}{\cal  K(\cal H)}
%\newcommand{\Real}{\mathbb R}
%\newcommand{\Complex}{\mathbb C}
%\newcommand{\Field}{\mathbb F}
%\newcommand{\RPlus}{[0,\infty)}
%
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\essnorm}[1]{\norm{#1}_{\text{\rm\normalshape ess}}}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\seq}[1]{\left<#1\right>}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\RE}{\operatorname{Re}}
\newcommand{\IM}{\operatorname{Im}}
\newcommand{\Poly}{{\cal{P}}(E)}
\newcommand{\EssD}{{\cal{D}}}

% THEOREMS ---------------------------------------------------------------
%\theoremstyle{plain}
%\newtheorem{thm}{Theorem}[section]


%
%\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]
\newcommand{\BD}{\begin{defn}}   \newcommand{\ED}{\end{defn}}
\newtheorem{con}[theorem]{Conjecture}
\newcommand{\BCONJ}{\begin{con}}   \newcommand{\ECONJ}{\end{con}}

%
%\theoremstyle{definition}
%\newtheorem{problem}[thm]{Problem}
\newcommand{\BPR}{\begin{problem}}   \newcommand{\EPR}{\end{problem}}

\newenvironment{rem}{\noindent{\bf Remark:~~}}{}
\newcommand{\BREM}{\begin{rem}} \newcommand{\EREM}{\end{rem}}
\newenvironment{discussion}{\noindent{\bf Discussion:~~\\}}{}
\newcommand{\BDIS}{\begin{discussion}} \newcommand{\EDIS}{\end{discussion}}
\newtheorem{obs}{Observation}[section]
%
\numberwithin{equation}{section}
\renewcommand{\theequation}{\thesection.\arabic{equation}}

\newcommand{\BPF}{\begin{proof}}
\newcommand{\EPF}{\end{proof}}
%%% ----------------------------------------------------------------------
%\setlength{\tclineskip}{1.05\baselineskip}
%%% ----------------------------------------------------------------------

%% My new commands
%\input psfig.sty
%\input{def}
\newcommand{\eqdef}{\triangleq}
\newcommand{\SSS}{\{0, \ldots, N-1 \}}


%\renewcommand{\baselinestretch}{1.66}

%\renewcommand{\baselinestretch}{1.15}

% following lines define subsubsection with counters
%\newcounter{msubsubsection}
%\renewenvironment{subsubsection}[1]
%    {\stepcounter{msubsubsection} $~$ \newline {\bf \large \arabic{chapter}.\arabic{section}.\arabic{subsection}.\arabic{msubsubsection} #1 \newline}}
%    {}

\allowdisplaybreaks



\title{\bf New results on $k$-independence of graphs}

\author{Shimon Kogan \\ 
  \small Department of Computer Science and Applied Mathematics \\[-0.8ex]
         \small Weizmann Institute, Rehovot 76100, Israel \\
          \small\tt shimon.kogan@weizmann.ac.il }
  \date{\dateline{Nov 24, 2015}{Mar 29, 2017}{May 5, 2017} \\
\small Mathematics Subject Classifications: 05C69}
  %\author{Shimon Kogan \\ \\
   %        kogan\_shimon@hotmail.com}

  %\date{\today}

  %\email{shimonk@wisdom.weizmann.ac.il}
\begin{document}
\maketitle
\begin{abstract}
Let $G = (V, E)$ be a graph and $k \geq 0$ an integer. A $k$-independent set
$S \subseteq G$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. Denote by $\alpha_{k}(G)$ the maximum cardinality of a $k$-independent set of $G$.  For a graph $G$ on $n$ vertices and average degree $d$, Tur\'an's theorem  asserts that $\alpha_{0}(G) \geq \frac{n}{d+1}$, where the equality holds if and only if $G$ is a union of cliques of equal size. For general $k$ we prove that $\alpha_{k}(G) \geq \dfrac{(k+1)n}{d+k+1}$, improving on the previous best bound $\alpha_{k}(G) \geq \dfrac{(k+1)n}{ \lceil d \rceil+k+1}$ of
Caro and Hansberg [E-JC, 2013]. For $1$-independence we prove that equality holds if and only if $G$ is either an independent set or a union of almost-cliques of equal size (an almost-clique is a clique on an even number of vertices minus a $1$-factor). For $2$-independence, we prove that equality holds
if and only if $G$ is an independent set. Furthermore when $d>0$ is an integer divisible by~3 we prove that  $\alpha_2(G) \geq \dfrac{3n}{d+3} \left( 1 + \dfrac{12}{5d^2 + 25d + 18} \right)$.
\end{abstract}


    %{
    %\WinEdt{?0000} % Don't bother with over/under-full boxes
    %\beforepreface
    %\WinEdt{?1111} % Process All Errors from Here on
    %}
   % \include{introduction}
   % \include{algorithm}
   % \include{np}
    %\include{hardness}
   % \include{bvc}
    %\#include{large}
    %\include{greedy}
    %\include{algorithm}
    %\include{multicoloring}
    %\include{Summary}

   % \appendix
    %\include{Appendix}

    % ------------------------------------------------------------------------
    %GATHER{thesis.bib}   % For Gather Purpose Only
    % \setlinespacing{1.44}
%    \bibliographystyle{amsplain}

\section{Introduction}
Let $G = (V, E) $ be a graph on $n$ vertices and let $k \geq 0$ be an integer. A $k$-independent set $S \subseteq V$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$.
Let $\alpha_{k}(G)$ denote the maximum cardinality of a $k$-independent set of $G$ and call it the $k$-independence number of G. For $k=0$ we have
$\alpha_{0}(G) = \alpha(G)$  where $\alpha(G)$ is the independence number of $G$. Let $d$ be the average degree of graph $G$.
Tur\'an's theorem \cite{turan} asserts that $\alpha(G) \geq \frac{n}{d+1}$, where equality holds if and only if $G$ is a union of cliques of equal size.
Tur\'an's bound was improved by the Caro-Wei bound \cite{caro2,wei1} which asserts that $\alpha(G) \geq \sum_{v \in V} \frac{1}{\text{deg}(v)+1}$, where equality holds if and only if $G$ is a union of cliques (see also \cite{noga1} page 95 for a proof).
The following two conjectures were made in \cite{caro3}:
\BCONJ\label{firstconj}
For a graph  $G$ on $n$ vertices and an integer $k \geq 1$, we have
\[
\alpha_{k}(G) \geq \frac{k+1}{d+k+1} n,
\]
where $d$ is the average degree of graph $G$.
\ECONJ
\BCONJ\label{secondconj}
For a graph  $G$ on $n$ vertices and an integer $k \geq 1$, we have
\[
\alpha_{k}(G) \geq \sum_{v \in V} \frac{k+1}{\text{deg}(v)+k+1}.
\]
\ECONJ
Conjecture \ref{firstconj}   follows from Conjecture \ref{secondconj} by Jensen's inequality. Hence Conjecture \ref{secondconj} is a strengthening of Conjecture \ref{firstconj}.
The first result on bounding $k$-independence was given in \cite{carotuza},
where it was shown that if $d \geq k+1$ then
\[ \alpha_{k}(G) \geq \frac{k+2}{2(d+1)} n. \]
Furthermore, an important step in proving Conjecture \ref{firstconj} was made in \cite[Theorem 18]{caro1},
where it was shown that if the average degree $d \geq 0$ is an integer then 
$$
\alpha_k(G) \geq \frac{(k+1)(d+2t)}{(d+k+t+1)(d+t)} n \geq \frac{k+1}{d+k+1} n,$$
where $t$ is such that $d \equiv k+1-t \pmod{k+1}$ and $1 \leq t \leq k+1$.
As a corollary they have the result
\[ \alpha_{k}(G) \geq \frac{k+1}{ \lceil d \rceil+k+1} n. \]

Now we shall describe our results.
An almost-clique is a clique on an even number of vertices minus a $1$-factor.
In this paper we prove that \[ \alpha_{1}(G) \geq \frac{2}{d+2} n, \] where equality holds
if and only if $G$ is either an independent set or a union of almost-cliques of equal size. 

For general $k$ we prove
$ \alpha_{k}(G) \geq \frac{k+1}{d+k+1} n$,
thus solving Conjecture \ref{firstconj}. 
More generally we prove that $\alpha_k(G) \geq f \negthinspace \left(\frac{d}{k+1}\right) n $,
where
\[
f(x) = \frac{1}{1+x} \left( 1 + \frac{ \{x\}\left( 1 - \{x\} \right) }{\left(\lfloor x \rfloor+1\right)\left(\lfloor x \rfloor+2\right)} \right)
\]
and where $\lfloor x \rfloor$ is the floor function and $\{x\}$ is the fractional part function. 


Notice that \cite[Theorem 18]{caro1} gives the same bound when $d$ is an integer. The novelty of our bound is that $d$ does not need to be an integer. 
Furthermore, we improve the bounds for $2$-independence, showing that if $d=3t$ for some integer $t>0$ then
\[
\alpha_2(G) \geq \frac{n}{t+1} \left( 1 + \frac{4}{15t^2 + 25t + 6} \right).
\]
This improves the bound in  \cite[Problem 23]{caro1} for $d=3t$, where the best previous bound was
$\alpha_2(G) \geq \frac{n}{t+1}$.
Finally we make modest progress on Conjecture \ref{secondconj} by showing that
\[
\alpha_{1}(G) \geq \sum_{v \in V} \frac{2}{\text{deg}(v)+2}
\]
holds for graphs $G$ of maximum degree at most $4$.

All along this paper, we will use the following notation and definitions.
Let $G$ be a graph.
$V(G)$ denotes the set of vertices of $G$ and $n(G) = |V (G)|$ denotes its cardinality.
$E(G)$ denotes the set of edges of $G$ and $e(G)$ denotes its cardinality.
For a vertex $v \in V (G)$, $\text{deg}(v) = \text{deg}_{G}(v)$ is the degree of $v$ in $G$.
By $\Delta(G)$ we denote the maximum degree of $G$
and by $d(G)$ the average degree $\frac{1}{n(G)} \sum_{v \in V(G)} \text{deg}(v)$.
The minimum degree of $G$ is denoted by $\delta(G)$.
For a subset $S \subseteq V (G)$, we write $G[S]$ for the graph induced by $S$ in $G$,
and $\text{deg}_{S} (v)$ stands for the degree  $\text{deg}_{G[S]} (v)$ of $v$ in $G[S]$.
For an integer $m > 1$, $m G$ is the graph consisting
of $m$ disjoint copies of $G$.
Lastly, for a vertex $v \in V (G)$, $G-v$ represents the graph $G$ without vertex $v$ and all the edges incident to $v$.

\section{Lower bounds on k-independence as a function of maximum degree}
For a graph $G$, we will denote by $\chi_{k}(G)$  the $k$-chromatic number of $G$, i.e. the minimum number $t$ such that there is a partition $V(G) = V_1(G) \cup V_2(G) \cup \ldots \cup V_t(G)$ of the vertex set $V(G)$ such that $\Delta(G[V_i]) \leq k$ for all $1 \leq i \leq t$. The following theorem is proven in \cite{lovlemma1}.
% we give a sketch of the proof for completeness.
\BTHM\label{lovlem}
Let $G$ be a graph with maximum degree $\Delta$. If $k_1, k_2, \ldots , k_t \geq 0$ are integers such that $\Delta+1 = \sum_{i=1}^t (k_i + 1)$, then there is a partition
$V(G) = V_1(G) \cup V_2(G) \cup \ldots \cup V_t(G)$ of the vertex set of $G$ such that
$\Delta(G[V_i]) \leq k_i $ for all $1 \leq i \leq t$.
\ETHM
%\BPF
%Let $P = (V_1,V_2,\ldots,V_t)$ be a partition of the vertices of $G$ into $k$ parts such that $V_1 \cup V_2 \cup \ldots \cup V_t = V(G)$. We define the function $\Phi(P)$ as
%\[
%\Phi(P) = \sum_{i=1}^t \left(e(G[V_i]) - k_i |V_i|\right)
%\]
%We shall show that a partition $P$ that minimizes $\Phi(P)$ satisfies $\Delta(G[V_i]) \leq k_i$ for all $1 \leq i \leq t$. \\
%Assume by contradiction by that $\Delta(G[V_i]) > k_i$ for some $1 \leq i \leq t$.
%Thus $G[V_i]$ contains a vertex $v$ such that  $\text{deg}_{V_i} (v) \geq k_i+1$.
%Notice that as $\Delta+1 = \sum_{i=1}^t (k_i + 1)$ we have that there is some index
%$1 \leq j \leq t$ such that $\text{deg}_{V_j} (v) \leq k_i$. Move vertex $v$ from $V_i$ to $V_j$
%and call the new partition $P'$. As $\Phi(P') < \Phi(P)$ we get a contradiction and we are done.
%\EPF
A partition as in the theorem above can be found in polynomial time. In \cite{magnus1} it is shown how to find such a partition in time $O(n^3)$.
\BCR
If $G$ is a graph of maximum degree $\Delta$ then $\chi_k(G) \leq \left \lceil \frac{\Delta + 1}{k+1} \right \rceil$.
\ECR
Now as $\alpha_k(G) \geq \frac{n}{\chi_k(G)}$ we get the following bound first proved in \cite{hopkins1}
\BTHM\label{lovbound}
Let $G$ be a graph of order $n$ and maximum degree $\Delta$. Then
\[
\alpha_k(G) \geq \frac{n}{\left \lceil \frac{\Delta + 1}{k+1} \right \rceil}.
\]
\ETHM
Furthermore, as the partition in Theorem \ref{lovlem} can be found in polynomial time, we also can find the $k$-independent set in Theorem \ref{lovbound} in polynomial time by picking the largest set in the partition. 

The bound in Theorem \ref{lovbound} is tight for $k=0$ and $k=1$. For $k=0$, an example of the sharpness of the bound is a union of cliques of equal size. For $k=1$, an example of the sharpness of the bound is a union of almost-cliques of equal size,
as noted in \cite{caro1}. 

For $k \geq 2$, the bounds of Theorem \ref{lovbound} can be improved in certain ranges by using
bounds on dominating sets. Recall that a set $S \subseteq  V$ is a dominating set of a graph $G = (V,E)$ if each vertex in $V$ is either in $S$ or is adjacent to a vertex in $S$.
The domination number $\gamma(G)$ is the minimum cardinality of a dominating set of $G$.
The following bound was proven in \cite{reed1}
\BTHM\label{reedbound}
If $G$ is a graph of order $n$ and minimum degree $\delta(G) \geq 3$, then
$\gamma(G) \leq \frac{3}{8} n$.
\ETHM

%Now we will convert the bound in Theorem \ref{reedbound} into a statement about $2$-independence
%by establishing a general connection between dominating sets and $k$-independece.

The following Theorem was proven in \cite[Theorem 3 (ii)]{DBLP:journals/dam/HansbergP13}.
\BTHM\label{dombound}
Let $k \geq 0$ be a fixed integer. If there is a constant $c$ such that for all $n$ every graph $G$ of order $n$ with minimum degree $\delta(G) \geq k+1$ satisfies  $\gamma(G) \leq c n$, then
 every graph $G$ of order $n$ and maximum degree $\Delta(G) \leq k+1$ satisfies $\alpha_{k}(G) \geq (1-c)n$.
\ETHM
%\BPF
%Let $k \geq 0$ be a fixed integer. \\[10pt]
%\emph{Assumption 1:} We assume that there is a constant $c$ such that for all $n$ every graph $G$ of order $n$ with minimum degree $\delta(G) \geq k+1$ satisfies  $\gamma(G) \leq c n$.
% \\[10pt]
%Let $G$ be a graph of order $n$ with maximum degree $\Delta(G) \leq k+1$. \\
%If $\delta(G) \geq k+1$ we have $\gamma(G) \leq c n$ by Assumption 1. Thus by removing a dominating set of size
%$c n$ from $G$ we get a $k$-independent set of size $(1-c) n$ and we are done.\\
%For the case $\delta(G) \leq k$ define the graph $G'$ which consist of $2(k+1)$ disjoint copies of $G$, that is $G'$ has vertex set $V_1 \cup V_2 \cup \ldots \cup V_{2(k+1)}$ and %$G'[V_i] = G$ for $1 \leq i \leq 2(k+1)$. \\
%We construct graph $G''$ from graph $G'$ in the following manner:
%Initially $G'' = G'$. Now for each vertex $v \in G$ such that $\text{deg}_G(v) \leq k$ take its $2(k+1)$ copies in $G''$ (that is its copies in $G'[V_1],G'[V_2] , \ldots , %G'[V_{2(k+1)}]$) and add between them $k+1-\text{deg}_G(v)$ disjoint perfect matchings. \\
%We conclude that $\delta(G'') = k+1$ and thus by assumption 1 we have
%$\gamma(G'') \leq 2c(k+1)n$. Let $T$ be a dominating set of size at most $2c(k+1)n$ in $G''$, by the pigeon principle there is an $i$ such that $\left|T \cap V_i\right| \leq c n$. Now %notice that
%$V_i \setminus T$ induces a $k$-independent set in $G$ as each vertex of degree $k+1$ in
%$G'[V_i]$ has a neighbor in $T \cap V_i$ or is in $T \cap V_i$ and we are done.
%\EPF
We will also need the following corollary also stated in \cite{DBLP:journals/dam/HansbergP13}.
\BCR\label{threebound}
Let $G$ be a graph of order $n$ with maximum degree $\Delta \leq 3$. Then $\alpha_2(G) \geq \frac{5}{8} n$.
\ECR
\BPF
Follows directly from combining Theorem \ref{dombound} and Theorem \ref{reedbound}.
\EPF
Generalizing Corollary \ref{threebound} we shall give improved bounds on $\alpha_2(G)$ in the case where the maximum degree of $G$ is divisible by 3.
\BTHM\label{threedeg_bound}
Let $G$ be a graph of order $n$ with maximum degree $\Delta \leq 3t$, for a natural number $t$. Then
$\alpha_2(G) \geq \frac{5}{5t+3} n$.
\ETHM
\BPF
We prove the statement by induction on $t$. The base case $t=1$ is proven in Corollary \ref{threebound}.
Assume that the theorem holds for $t-1$ and we will prove for $t$.
Let $G$ be a graph of order $n$ and maximum degree $\Delta \leq 3t$. By Theorem \ref{lovlem}
there is a partition
$V(G) = V_1(G) \cup V_2(G)$ of the vertex set of $G$ such that $\Delta(G[V_1]) \leq 3t-3$ and
$\Delta(G[V_2]) \leq 2$. \\
If $\left| V_2 \right| \geq \frac{5}{5t+3} n$ we are done, because $\Delta(G[V_2]) \leq 2$.
Thus we may assume that $\left| V_1 \right| \geq \frac{5t-2}{5t+3} n$. Applying the induction
hypothesis on $G[V_1]$ we conclude that
\[
\alpha_2(G[V_1]) \geq \frac{5}{5t-2}\cdot \frac{5t-2}{5t+3} \cdot n = \frac{5}{5t+3} n
\]
and we are done.
\EPF
\BCR
Let $G$ be a graph of order $n$ with maximum degree $\Delta>0$, where $\Delta$ is divisible by 3. Then
$\alpha_2(G) \geq \frac{15}{5\Delta+9} n$.
\ECR

\section{Lower bounds on $k$-independence in terms of average degree}
\BD\label{mainfuncdef1}
Define the function $f(x)$ for real  $x \geq 0$ in the following manner:
\[
f(x) = \frac{1}{1+x} \left( 1 + \frac{ \{x\}\left( 1 - \{x\} \right) }{\left(\lfloor x \rfloor+1\right)\left(\lfloor x \rfloor+2\right)} \right),
\]
where $\lfloor x \rfloor$ is the floor function and $\{x\}$ is the fractional part function.
\ED
\BL\label{simplebound}
Let $x \geq 0$ be a real number. Then $f(x) \geq \frac{1}{1+x}$, and equality holds if and only if $x$ is an integer.
\EL
\BPF
Notice that for any real  $x \geq 0$ we have
\[
\frac{ \{x\}\left( 1 - \{x\} \right) }{\left(\lfloor x \rfloor+1\right)\left(\lfloor x \rfloor+2\right)} \geq 0,
\]
and the equality holds if and only if $x$ is an integer, and thus we are done.
\EPF
In this section we will prove the following theorem:
\BTHM \label{general_bound1}
Let $k \geq 0$ be an integer. Then for any graph $G$ of order $n$ and average degree $d$ we have
\[
  \alpha_k(G) \geq f \negthinspace \left(\frac{d}{k+1}\right) n.
\]
\ETHM
\BCR \label{general_bound2}
Let $k \geq 0$ be an integer. Then for any graph $G$ of order $n$ and average degree $d$ we have
\[
  \alpha_k(G) \geq \frac{k+1}{d+k+1} n.
\]
\ECR
\BPF
This follows from  Theorem \ref{general_bound1} and Lemma \ref{simplebound}, as
\[
  \frac{1}{1 + \frac{d}{k+1}} = \frac{k+1}{d+k+1}.\qedhere
\]
\EPF
We note that Theorem \ref{general_bound1} was proven for the case where the average degree $d$ of graph $G$
is an integer in \cite{caro1} (Theorem 3.7). Here we prove it in full generality. The difference between our proof and the proof in \cite{caro1} is that we make the induction on the ranges of the degrees, while in \cite{caro1} the induction is on the average degree as an integer.
Before proving Theorem \ref{general_bound1} we will need a few more lemmas and definitions.
\BD\label{mainfuncdef2}
Define a function $g(x)$ for real  $x \geq 0$ in the following manner:
\[
g(x) =
\begin{cases}
1,          &\text{if $x = 0$} \\
\dfrac{2\lceil x \rceil - x}{\lceil x \rceil \left( 1+\lceil x \rceil \right)}, &\text{if $x > 0$}.
\end{cases}
\]
where $\lceil x \rceil$ is the ceiling function.
\ED
\BL\label{mainlem1}
For all real $x \geq 0$ we have $f(x) = g(x)$.
\EL
\BPF
First notice that
\[
g(x) = \frac{2 \lfloor x \rfloor + 2 - x}{\left( \lfloor x \rfloor + 1 \right)
 \left( \lfloor x \rfloor + 2 \right) }.
\]
This follows from the fact that if $x$ is not an integer then
 $\lceil x \rceil = \lfloor x \rfloor + 1$, while if $x=n$ for some integer $n \geq 0$ then
 $g(n) = f(n) = \frac{1}{n+1}$.
We conclude that
\begin{align}
g(x) - \frac{1}{x+1} &=  \frac{2 \lfloor x \rfloor + 2 - x}{\left( \lfloor x \rfloor + 1 \right)
 \left( \lfloor x \rfloor + 2 \right) } - \frac{1}{x+1} \notag \\
 &= \frac{
 \left( 2 \lfloor x \rfloor + 2 - x \right)\left( x+1\right)
  - \left( \lfloor x \rfloor + 1 \right)
 \left( \lfloor x \rfloor + 2 \right)}{\left( x + 1 \right) \left( \lfloor x \rfloor + 1 \right)
 \left( \lfloor x \rfloor + 2 \right) } \notag \\
 &= \frac{\left( x - \lfloor x \rfloor \right) - \left( x - \lfloor x \rfloor \right)^2}
 { \left( x + 1 \right) \left( \lfloor x \rfloor + 1 \right)
 \left( \lfloor x \rfloor + 2 \right)} \notag \\
 &= \frac{\{x\}\left( 1 - \{x\} \right)}
 {\left( x + 1 \right) \left( \lfloor x \rfloor + 1 \right)
 \left( \lfloor x \rfloor + 2 \right)} \notag \\
 &= f(x) - \frac{1}{x+1}. \notag
\end{align}
and we are done.
\EPF
\BL\label{fproperties}
The function $f(x)$ is continuous, monotonically decreasing and convex on the interval $[0,\infty)$.
\EL
\BPF
As $f(x) = g(x)$ for $x\geq 0$, it suffices to prove the claim for $g(x)$.
The continuity of $g(x)$ for $x\geq 0$ follows from the fact that
\[
\lim_{x \to 0^+} g(x) = 1 = g(0),
\]
and for any integer $n \geq 1$
\[
\lim_{x \to n^-} g(x) = \lim_{x \to n^+} g(x) = \frac{1}{n+1} = g(n).
\]
Now as the function $g(x)$ is continuous and monotonically decreasing on each interval
$[n,n+1]$ for any integer $n \geq 0$, it follows that $g(x)$ is monotonically decreasing on the interval $[0,\infty)$. \\
To prove convexity we will use the following fact: \\
If a function is continuous on an open interval I and possesses a non-decreasing
right-derivative on I, then the function is convex on I (this is Theorem 5.3.1 in \cite{convexbook}). \\
Notice that for every integer $n \geq 0$ the right-derivative of $g(x)$ on the interval $[n,n+1)$
satisfies
\[
g'(x^+) = -\frac{1}{(n+1)(n+2)},
\]
hence the right-derivative of $g$ is non-decreasing in the interval $(0,\infty)$. We conclude that
$g(x)$ is convex in the interval $(0,\infty)$. Finally, by the continuity of $g(x)$, we can extend the convexity to the interval $[0,\infty)$, and we are done.
\EPF
\BL\label{mainlem2}
Let $k \geq 0$ and $r \geq 0$ be integers. Let $G$ is a graph of order $n$ with $e$ edges and average degree $d = \frac{2e}{n}$. If $r(k+1) < d  \leq (r+1)(k+1)$ holds and
\[
\alpha_k(G) \geq \frac{2}{r+2} \left( n - \frac{e}{(r+1)(k+1)} \right),
\]
then $\alpha_k(G) \geq f \negthinspace \left( \frac{d}{k+1} \right) n$.
\EL
\BPF
Set $t=\frac{d}{k+1}$.
As $r(k+1) < d \leq (r+1)(k+1)$ we have $r < t \leq r+1$. \\ Hence $\lceil t \rceil = r+1$.
Thus we have
\begin{align*}
\alpha_k(G) &\geq \frac{2}{r+2} \left( n - \frac{e}{(r+1)(k+1)} \right) \\
            &= \frac{2}{\lceil t \rceil+1} \left( n - \frac{d n}{2\lceil t \rceil(k+1)} \right)
            &&\text{(as $r+1 = \lceil t \rceil)$ }\\
            &=  \frac{2}{\lceil t \rceil+1} \left( n - \frac{t n}{2\lceil t \rceil} \right)
            &&\text{\Big(as $t=\frac{d}{k+1}$\Big) }\\
            &=  \frac{2n}{\lceil t \rceil+1} \left( 1 - \frac{t}{2\lceil t \rceil} \right) \\
            &= n \frac{2\lceil t \rceil - t}{\lceil t \rceil \left( 1+\lceil t \rceil \right)}
            = g(t) n = f(t) n &&\text{(by Lemma \ref{mainlem1})}
\end{align*}
and we are done.
\EPF
\BL\label{mainlem3}
Let $k \geq 0$ be an integer. If $G$ is a graph of order $n$ with $e$ edges then
\[
\alpha_k(G) \geq n - \frac{e}{k+1}.
\]
\EL
\BPF
Set $G_0 = G$. If there is a vertex $v_0 \in V(G_0)$ such that $\text{deg}_{G_0}(v_0) \geq k+1$ remove
it from the graph $G_0$ and call the resulting graph $G_1$ (that is, $G_1 = G_0 - v_0$). \\
Now, if there is a vertex $v_1 \in V(G_1)$ such that $\text{deg}_{G_1}(v_1) \geq k+1$ remove
it from the graph $G_1$ and call the resulting graph $G_2$ (that is, $G_2 = G_1 - v_1$). \\
We can repeat this operation iteratively  until we get a graph $G_i$ for some $i \geq 0$ such that
the maximum degree of $G_i$ satisfies $\Delta(G_i) \leq k$. Notice that
$i \leq \left\lfloor \frac{e}{k+1} \right\rfloor$, as there are $e$ edges in $G_0$, and in each iteration the number of edges in the resulting graph is decreased by at least $k+1$. Hence
if we have reached iteration $t$ for  $t = \left\lfloor \frac{e}{k+1} \right\rfloor$, then graph $G_t$ will contain at most
$e - (k+1)\left\lfloor \frac{e}{k+1} \right\rfloor \leq k$ edges, and thus $G_t$ is a $k$-independent set, which means that $i \leq t$.
Since $V(G_i)$ is a $k$-independent set in $G$ and $|V(G_i)| = n - i \geq n - \frac{e}{k+1}$, we are done.
\EPF
\BCR\label{main_induction_base}
Let $k \geq 0$ be an integer. If $G$ is a graph of order $n$ with average degree $0 < d \leq k+1$,
then $\alpha_k(G) \geq f \negthinspace \left( \frac{d}{k+1} \right) n$.
\ECR
\BPF
This follows from Lemma \ref{mainlem3} by setting $r=0$ in Lemma \ref{mainlem2}.
\EPF
Finally we are ready to prove the main theorem of this section.
\medskip

\noindent\textbf{Proof of Theorem \ref{general_bound1}:} \\
Let $k \geq 0$ be an integer.
Recall that we need to prove that for any graph $G$ of order $n$ and average degree $d$ we have
\[
  \alpha_k(G) \geq f \negthinspace \left(\frac{d}{k+1}\right) n.
\]
We will prove by induction on integer $r \geq 0$ that for any graph $G$ of order $n$ and average degree $d \leq (r+1)(k+1)$ we have:
\[
  \alpha_k(G) \geq f \negthinspace \left(\frac{d}{k+1}\right) n.
\]
The base of the induction $r=0$ was proven in Corollary \ref{main_induction_base}.
We will assume that the claim holds for $r-1 \geq 0$ and we will prove for $r$. 

By Lemma \ref{mainlem2} and the induction hypothesis, it suffices to prove
that that if $G$ is a graph on $n$ vertices, $e$ edges and average degree $d$ satisfying $r(k+1) < d  \leq (r+1)(k+1)$, then
\[
\alpha_k(G) \geq \frac{2}{r+2} \left( n - \frac{e}{(r+1)(k+1)} \right).
\]
We can assume that both $n$ and $e$ are divisible by $(r+2)(k+1)$.
This is because we can build a graph $G' = (r+2)(k+1)G$ (namely,
$G'$ is a disjoint union of $(r+2)(k+1)$ copies of $G$), where $d(G) = d(G')$,
and the number of vertices $n'$ and number of edges $e'$ of $G'$ are both divisible by $(r+2)(k+1)$.
If $\alpha_k(G') \geq n' f \negthinspace\left(\frac{d}{k+1} \right)$ then the original graph $G$ satisfies
\[
\alpha_k(G) \geq \frac{n'}{(r+2)(k+1)} f \negthinspace\left(\frac{d}{k+1} \right) = n f \negthinspace\left(\frac{d}{k+1} \right)
\]
(this observation which greatly simplifies the proof is essentially taken from
\cite[Lemma 16]{caro1}). 

We define parameter $t$ as follows:
\[
t = \frac{2e - nr(k+1)}{(r+2)(k+1)}.
\]
Notice that $t$ is an integer (because $n$ and $e$ are divisible by $(r+2)(k+1)$),
and that $t > 0$ (because $d > r(k+1)$). 

Set $G_0 = G$. If there is a vertex $v_0 \in V(G_0)$ such that
$\text{deg}_{G_0}(v_0) \geq (r+1)(k+1)$, remove
it from the graph $G_0$ and call the resulting graph $G_1$ (that is, $G_1 = G_0 - v_0$). 

Now if $t>1$ and there is a vertex $v_1 \in V(G_1)$ such that $\text{deg}_{G_1}(v_1) \geq (r+1)(k+1)$, remove
it from the graph $G_1$ and call the resulting graph $G_2$, (that is, $G_2 = G_1 - v_1$). 

We repeat this operation iteratively, that is on iteration $i$ (starting with $i=0$)  we first check if $i=t$ or $\Delta(G_i) < (r+1)(k+1)$,
and if one of these conditions holds we terminate the process. Otherwise, we pick a vertex $v_i \in V(G_i)$ such that $\text{deg}_{G_i}(v_i) \geq (r+1)(k+1)$ and remove it from the graph $G_i$. We call the resulting graph $G_{i+1}$ (that is $G_{i+1} = G_i - v_i$). 

Suppose that the process above terminated on iteration $j \leq t$ (that is, the last graph created in the process is $G_j$). If $j<t$ then $\Delta(G_j) < (r+1)(k+1)$, and thus by Theorem \ref{lovbound} we have $\alpha_k(G_j) \geq \frac{n-t}{r+1}$. Now we shall prove that if $j=t$ we also have $\alpha_k(G_j) \geq \frac{n-t}{r+1}$. 

First we notice that
\begin{align}
n-t &= n - \frac{2e - nr(k+1)}{(r+2)(k+1)} \notag \\
    &= \frac{(r+2)(k+1)n + nr(k+1) - 2e}{(r+2)(k+1)} \notag \\
    &= \frac{2[n(r+1)(k+1) - e]}{(r+2)(k+1)}. \label{nminust}
\end{align}
Now we claim that $d(G_t) \leq r(k+1)$.
Notice that as in each iteration at least $(r+1)(k+1)$ edges were removed we have that
$e(G_t)$ (the number of edges in graph $G_t$) satisfies
\begin{align}
e(G_t) &\leq e - t(r+1)(k+1) \notag \\
        &= e - \frac{(r+1)(2e - nr(k+1))}{r+2} \notag \\
        &= \frac{nr(r+1)(k+1) - e r}{r+2} \notag \\
        &= \frac{r[n(r+1)(k+1) - e]}{r+2} \notag \\
        &= \frac{1}{2} (k+1)r(n-t) &&\text{(by Equation \ref{nminust})}. \notag
\end{align}
It follows that
\[
d(G_t) = \frac{2e(G_t)}{n-t} \leq r(k+1).
\]
Now as $d(G_t) \leq r(k+1)$ we can apply the induction hypothesis on $G_t$. By the induction hypothesis and Lemma \ref{simplebound} we have
\[
\alpha_k(G_t) \geq \frac{n-t}{r+1}.
\]
We conclude that
\begin{align}
\alpha_k(G) &\geq \alpha_k(G_j) \notag \\
 &\geq \frac{n-t}{r+1} \notag \\
&= \frac{2}{r+2} \left( n - \frac{e}{(r+1)(k+1)} \right) &&\text{(by Equation \ref{nminust})} \notag \\
&\geq f \negthinspace \left( \frac{d}{k+1} \right) n &&\text{(by Lemma \ref{mainlem2})} \notag
\end{align}
and that is exactly what we needed to prove.
This concludes the proof of the induction. \qed

\medskip

The proof of Theorem \ref{general_bound1} gives a polynomial time algorithm
for finding a $k$-independent set of cardinality at least
$f \negthinspace \left( \frac{d(G)}{k+1} \right) n$ for any graph $G$ on $n$ vertices.
\\ \text{}

\fbox{
\begin{minipage}{14.5 cm}
 \textbf{Algorithm I} \\ \text{} \\
 \textbf{Input:} \hspace{3.5pt} A graph $G$ on $n$ vertices and $e$ edges.\\
 \textbf{Output:} A $k$-independent set $S$ of size at least
 $f \negthinspace \left( \frac{d(G)}{k+1} \right) n$.
 \begin{enumerate}
 \item Set $i=0$, $G_0 = G$, $B = f \negthinspace \left( \frac{d(G)}{k+1} \right) n$ and GOTO 2.
 \item If
 $
 n(G_i) \geq
 \left\lceil \frac{\Delta(G_i)+1}{k+1}\right\rceil B
 $
 then apply Theorem \ref{lovbound} to find a $k$-independent set $S$ in $G_i$ of size at least
 $B$ and END. Otherwise GOTO 3.
 \item Choose a vertex $v$ of maximum degree in $G_i$, set $G_{i+1} = G_i - v$, set $i=i+1$ and GOTO 2.
 \end{enumerate}
\end{minipage}
}
\\[10pt] \text{}

The correctness of the algorithm follows directly from the proof of Theorem \ref{general_bound1}.
Notice however that at certain points in the proof of Theorem \ref{general_bound1} we take our
graph and expand it to a union of several disjoint copies of the graph. This does not affect
the validity of Algorithm 1 because a removal of a vertex $v$ in algorithm I corresponds to the removal of the same vertex $v$ from each copy in the extended graph until it is exhausted from all copies (as it remains a vertex of maximum degree). Finally as the procedure in Theorem  \ref{lovbound} has running time $O(n^3)$, Algorithm I has running time of $O(n^3)$ too.

\section{The case of equality for the 1-independence bound}

Given a graph $G$ of order $n$ with average degree $d$ and $e$ edges, the combination of Theorem \ref{general_bound1} and Lemma \ref{simplebound} implies that
\begin{align}
\alpha_1(G) &\geq f\left(\frac{d}{2}\right) \geq \frac{2}{d+2} n = \frac{n^2}{n+e} &&\text{\Big(as $d=\frac{2e}{n}$\Big)} \label{ebound1}
\end{align}
Recall that an almost-clique is a clique on an even number of vertices minus a $1$-factor.
Let $t$ be an even integer. We denote by $J_t$ an almost clique on $t$ vertices.
In this section we shall show that $\alpha_1(G) =  \frac{2}{d+2} n$
if and only if $G$ is either an independent set or a union of almost-cliques of equal size. 

First of all it is clear that for all even integers $t \geq 2$ we have
\[
\alpha_1(J_t) = 2 = \frac{2}{d\left(J_t\right)+2} t.
\]
This was first stated in \cite[Theorem 17]{caro1}.
Now we shall prove that if $\alpha_1(G) =  \frac{2}{d+2} n$ then $G$ is either an independent or a union of almost-cliques of equal size. We will do so in a series of lemmas.
\BL\label{equalb1}
Let $G$ be a graph of order $n$ and average degree $d$. If $\alpha_1(G) = \frac{2}{d+2} n$ then $d$ is an even integer.
\EL
\BPF
This follows from Theorem \ref{general_bound1} and Lemma \ref{simplebound}.
\EPF
\BL\label{equalb2}
Let $k \geq 0$ be integer. Let $G$ be a graph of order $n$ with average degree $d(G) = 2k$. If $\alpha_1(G) = \frac{n}{k+1}$ then $G$ is $2k$-regular (that is all its vertices are of degree $2k$).
\EL
\BPF
The claim is trivial for $k=0$ and for the case $n\leq 2$. Henceforth we assume that $k\geq 1$ and $n \geq 3$.
Suppose (by contradiction) that $G$ is not $2k$-regular. Then from the fact that $d(G) = 2k$ we know that $G$ contains a vertex $v$ of degree at least $2k+1$. Remove vertex $v$ from $G$ and call the resulting graph $G'$ (that is, $G' = G - v$). 

Thus we have
\begin{align*}
\alpha_1(G) &\geq \alpha_1(G')\\
&\geq \frac{(n-1)^2}{e(G')+n-1} &&\text{(by Equation \ref{ebound1})} \\
&\geq \frac{(n-1)^2}{kn -2k - 1 +n-1} &&\text{(as $e(G') \leq kn - (2k+1)$)} \\
&= \frac{(n-1)^2}{(n-2)(k+1)} \\
&> \frac{n}{k+1} &&\text{(as $(n-1)^2 > n(n-2)$)}
\end{align*}
We got a contradiction and the proof follows.
\EPF
Recall that $C_n$ is a cycle on $n$ vertices and $P_n$ is a path on $n$ vertices.
Notice that the almost clique on $4$ vertices is simply a cycle on $4$ vertices, that is $J_4 = C_4$.
\BL\label{c4lem}
Let $G$ be a graph of order $n$ and maximum degree $\Delta(G) \leq 2$. If $\alpha_1(G) = \frac{n}{2}$ then $G$ is a union of copies of $C_4$.
\EL
\BPF
Each connected component of $G$ is either a path or a cycle.
Now notice that for all integers $n>0$ we have $\alpha_1(P_n) \geq \frac{2}{3} n$, and thus for all $n\geq 3$ we have  $\alpha_1(C_n) \geq \frac{2}{3} (n-1)$. It follows that $\alpha_1(P_n) > n/2$ for all $n>0$, and that
 $\alpha_1(C_n) = n/2$ if and only if $n=4$. This concludes the proof.
\EPF

\BL\label{equalb3}
Let $k \geq 1$ be integer. Let $G$ be a graph of order $n$ and maximum degree $\Delta(G) \leq 2k$. If $\alpha_1(G) = \frac{n}{k+1}$ then $G$ is a union of copies of $J_{2k+2}$.
\EL

\BPF
We will prove the claim by induction on $k$.
The base of the induction $k=1$ is simply Lemma  \ref{c4lem}.
 Assume that the claim holds for $k-1$ and we will prove it for $k$. 
 
Let $G$ be a graph of order $n$ and maximum degree $\Delta(G) \leq 2k$.
Assume that $\alpha_1(G) = \frac{n}{k+1}$.
By Theorem \ref{lovlem}
there is a partition $V(G) = V_1(G) \cup V_2(G)$ of the vertex set of $G$ such that $\Delta(G[V_1]) \leq 2k-2$ and  $\Delta(G[V_2]) \leq 1$.

Let $G_1 = G[V_1]$ be a graph on $n_1$ vertices and $G_2 = G[V_2]$ be a graph on $n_2$ vertices.
Observe that $n_2 \leq \frac{n}{k+1}$, as $G_2$ is a $1$-independent set.
If $n_1 > \frac{k}{k+1} n$, then by Theorem \ref{lovbound} and the fact that $\Delta(G_1) \leq 2k-2$,
we have $\alpha_1(G_1) > \frac{n}{k+1}$. Thus $n_1 \leq \frac{k}{k+1} n$. 

As $n_1 \leq \frac{k}{k+1} n$,  $n_2 \leq \frac{1}{k+1} n$ and $n_1 + n_2 = n$,  we conclude that
$n_1 = \frac{k}{k+1} n$ and $n_2 = \frac{1}{k+1} n$. 
Since $n_1 = \frac{k}{k+1} n$ and $\Delta(G_1) \leq 2k-2$ we have by Theorem \ref{lovbound}
that $\alpha_1(G_1) \geq \frac{n}{k+1}$.
Thus we have
 \[
   \frac{n}{k+1} = \alpha_1(G) \geq \alpha_1(G_1) \geq \frac{n}{k+1}
 \]
and we conclude that $\alpha_1(G_1) = \frac{n}{k+1}$. 

Finally, as $G_1$ has exactly $n_1 = \frac{k}{k+1} n$ vertices, maximum degree $\Delta(G_1) \leq 2k-2$  and $\alpha_1(G_1) = \frac{n}{k+1}$, we have by the induction hypothesis that $G_1$ is a union of copies of $J_{2k}$. \\ Let the copies of $J_{2k}$ in $G_1$ be $U_1,U_2, \ldots, U_t$ where
$t=\frac{n}{2(k+1)}$ (that is, $G_1 = U_1 \cup U_2 \cup \ldots \cup U_t$).
Let $v$ be an arbitrary vertex of $G_2$. We claim that $v$ (as a vertex of $G$) is adjacent to all the $2k$ vertices of $U_i$ for some $i$. Suppose (for the sake of contradiction) that this does not hold. Then there
are two cases. 

\emph{Case 1:} For all $i\geq 1$, $v$ is adjacent to at most $2k-2$ vertices of $U_i$.\\
In this case we can pick from each $U_i$ two vertices that are not adjacent to $v$ (this is possible as $k \geq 2$). Call the resulting set $S$. Notice that $S \cup \{v\}$ is a $1$-independent set in $G$ of size $2t+1 > \frac{n}{k+1}$.
We get a contradiction and thus this case is done. 

\emph{Case 2:} There are $i,j \geq 1$ such that $v$ is adjacent to $2k-1$ vertices in
$U_i$, is adjacent to at most one vertex of $U_j$, and $v$ is not adjacent to any other vertex in $G_1$.


In this case we pick arbitrarily two vertices from each $U_k$, where $k\neq i$ and $k\neq j$.
Call the resulting set $S$.
Now we pick a vertex $u_1$ from $U_i$ which is not adjacent to $v$. As $J_{2k}$ is a clique minus a $1$-factor there is a vertex $u_2$ in $U_i$ such that $u_1$ and $u_2$ are not adjacent.
We add $u_1$ and $u_2$ to the set $S$. Finally we pick vertices $u_3$ and $u_4$ in $U_j$
such that $u_3$ and $u_4$ are not adjacent to $v$. This is possible as $k\geq 2$ and $v$ is adjacent to at most one vertex in $U_j$. Add $u_3$ and $u_4$ to the set $S$.
Notice that $S \cup \{v\}$ is a $1$-independent set in $G$ of size $2t+1 > \frac{n}{k+1}$. Once again we got a contradiction.

We have shown that each vertex $v$ in $G_2$ is adjacent to all the $2k$ vertices of $U_i$ for some $i$ (dependent on $v$). We conclude that $G$ is a union of copies of $J_{2k+2}$, and thus we are done.
\EPF

Finally we are ready to prove the main theorem of this section.
\BTHM
Let $G$ be a graph of order $n$ and average degree $d$. If $\alpha_1(G) =  \frac{2}{d+2} n$
then $G$ is either an independent set or a union of almost-cliques of equal size.
\ETHM
\BPF
The case $d=0$ is trivial as then the graph $G$ must be an independent set.
We will assume henceforth that $d>0$.
By Lemma \ref{equalb1} the average degree $d$ must be an even integer. Let $d=2k$ for some integer $k \geq 1$.
By Lemma \ref{equalb2} we have that $G$ is in fact $2k$-regular.
Finally by Lemma \ref{equalb3} graph $G$ is a union of copies of $J_{2k+2}$, and we are done.
\EPF

\section{Caro-Wei type bound for 1-independence}

Let $f(x)$ be the function from Definition \ref{mainfuncdef1}, that is for real $x\geq 0$
\[
f(x) = \frac{1}{1+x} \left( 1 + \frac{ \{x\}\left( 1 - \{x\} \right) }{\left(\lfloor x \rfloor+1\right)\left(\lfloor x \rfloor+2\right)} \right).
\]
For all integers $k \geq 0$ and real $x \geq 0$ define $f_k(x) = f \negthinspace \left(\frac{x}{k+1}\right)$.
\BL\label{fkproperties}
For any integer $k\geq 0$ and for $x$ in the interval $[0,\infty)$, the function $f_k(x)$ is continuous, monotonically decreasing and convex.
\EL
\BPF
The proof of continuity and that the function is monotonically decreasing is almost identical to the proof of Lemma  \ref{fproperties} and thus omitted.
The convexity of $f_k(x)$ follows from the convexity of $f(x)$ as proven in Lemma \ref{fproperties}, combined with the fact that the composition of a convex function with an affine function is convex.
\EPF
\BCR\label{minusineq1}
For all integers $k\geq 0$  and $n \geq 1$ we have $f_k(n-1) - f_k(n) \geq f_k(n) - f_k(n+1)$.
\ECR
\BPF
This inequality follows from the convexity of the function $f_k(x)$ on the interval $[0,\infty)$.
\EPF
In this section we shall make the following conjecture:
\BCONJ\label{our_conjecture}
Let $G$ be a graph of order $n$ with degree sequence $d_1, \ldots , d_n$. Then
\[
\alpha_{k}(G) \geq \sum_{i=1}^n f_k\left( d_i \right)
\]
\ECONJ
For $k=0$ the conjecture above is simply the Caro-Wei bound.
Thus the first open case is the case when $k=1$. This conjecture seems to be significantly harder
than Conjecture \ref{firstconj}. Notice that Conjecture \ref{our_conjecture} implies Conjecture
\ref{secondconj} (by Lemma \ref{simplebound}).
Furthermore, by Jensen's inequality, Theorem \ref{general_bound1} follows directly from Conjecture \ref{our_conjecture}.
In this section we shall make a very modest progress by
proving that the $k=1$ case of Conjecture \ref{our_conjecture} holds
for graphs of maximum degree $4$. 

For integers the following formulation of the function $f_1$ is easier to work with.
\BL
For all integers $n\geq 0$ we have
\[
f_1(n) =
\begin{cases}
\frac{2}{n+2},        &\text{if $n$ is even}\\
\frac{1}{n+1} + \frac{1}{n+3},         &\text{if $n$ is odd}.
\end{cases}
\]
\EL
\BPF
Follows directly from Definition \ref{mainfuncdef1}.
\EPF
The first few values of $f_1$ are: $f_1(0) = 1$, $f_1(1) = \frac{3}{4}$,
$f_1(2) = \frac{1}{2}$, $f_1(3) = \frac{5}{12}$ and $f_1(4) = \frac{1}{3}$.
\BD
Given a graph $G$. Define
\[
s(G) = \sum_{v \in V(G)} f_1 \left( \text{deg}_{G}(v)\right).
\]
\ED
We are ready to prove the main result of this section.
\BTHM
If $G$ is a graph of order $n$ with maximum degree $\Delta(G) \leq 4$ then $\alpha_1(G) \geq s(G)$
\ETHM
\BPF
We proceed by induction on $n$. For $n=1$ the claim is trivial.
Now we will assume that the claim holds for graphs on at most $n-1$ vertices, and we will prove the claim for graphs on $n$ vertices. 

Assume we have a graph $G$ with $n \geq 2$ vertices. If $\Delta(G) \leq 1$ the claim holds trivially
as $G$ is a $1$-independent set in this case.
Hence we may assume that $2 \leq \Delta(G) \leq 4$.
Furthermore, we may assume that graph $G$ is connected, for otherwise we can apply the inductive hypothesis to each connected component.
Now we will consider 3 cases.
\medskip

\emph{Case 1:} $\Delta(G) = 4$ \\
Let $v$ be a vertex of maximum degree in $G$. Define graph $G'$ as $G' = G - v$.
Let $v_1,v_2,v_3,v_4$ be the neighbors of $v$ in $G$.
\[
s(G') = s(G) - f_1(\text{deg}_G(v)) + \sum_{i=1}^4
\left[ f_1(\text{deg}_G(v_i) - 1) - f_1(\text{deg}_G(v_i))  \right].
\]
Hence to prove that $s(G') \geq s(G)$ it suffices to show that
\[
\sum_{i=1}^4
\left[ f_1(\text{deg}_G(v_i) - 1) - f_1(\text{deg}_G(v_i))  \right]
\geq f_1(\text{deg}_G(v)),
\]
This follows as
\begin{align*}
\sum_{i=1}^4
\left[ f_1(\text{deg}_G(v_i) - 1) - f_1(\text{deg}_G(v_i))  \right]
&\geq \sum_{i=1}^4 \left[ f_1(3) - f_1(4)  \right] &&\text{(by Corollary \ref{minusineq1})} \\
&= 4(\frac{5}{12} - \frac{1}{3}) \\ % &&\text{(as $f_1(3) = \frac{5}{12}$ and $f_1(4) = \frac{1}{3}$)} \\
&= \frac{1}{3} = f_1(4) = f_1(\text{deg}_G(v)).
\end{align*}
Hence, we obtain $s(G') \geq s(G)$. Combined with $\alpha_1(G) \geq \alpha_1(G')$ and $\alpha_1(G') \geq s(G')$, which is given by the induction hypothesis,
the claim follows. 

\medskip
\emph{Case 2:} $\Delta(G) = 3$ \\
If $G$ is a $3$-regular graph then by Theorem \ref{lovbound} we have $\alpha_1(G) \geq \frac{1}{2} n > \frac{5}{12}n = s(G)$ (as $f_1(3) = \frac{5}{12}$) and we are done. 

The remaining case is when $G$ is a connected graph of maximum degree $3$, which contains a vertex of degree $3$ and also a vertex of degree at most $2$. Thus $G$ contains a vertex $v$ of degree $3$ with at least one neighbor of degree at most $2$. Let $v_1,v_2,v_3$ be the neighbors of $v$ in $G$ and assume that
$\text{deg}_G(v_1) \leq 2$. Define graph $G'$ as $G' = G - v$ and notice that
\[
s(G') = s(G) - f_1(\text{deg}_G(v)) + \sum_{i=1}^3
\left[ f_1(\text{deg}_G(v_i) - 1) - f_1(\text{deg}_G(v_i))  \right].
\]
Now
\begin{align*}
 \sum_{i=1}^3
\left[ f_1(\text{deg}_G(v_i) - 1) - f_1(\text{deg}_G(v_i))  \right]
&\geq (f_1(1) - f_1(2)) + 2(f_1(2) - f_1(3)) \\
&= \frac{5}{12} = f_1(3) = f_1(\text{deg}_G(v)).
\end{align*}
Hence $s(G') \geq s(G)$, and thus the claim follows by the induction hypothesis.

\medskip
\emph{Case 3:} $\Delta(G) = 2$ \\
Let $v$ be a vertex of maximum degree in $G$. Define graph $G'$ as $G' = G - v$.
Let $v_1,v_2$ be the neighbors of $v$ in $G$.
\[
s(G') = s(G) - f_1(\text{deg}_G(v)) + \sum_{i=1}^2
\left[ f_1(\text{deg}_G(v_i) - 1) - f_1(\text{deg}_G(v_i))  \right].
\]
Notice that
\begin{align*}
\sum_{i=1}^2
\left[ f_1(\text{deg}_G(v_i) - 1) - f_1(\text{deg}_G(v_i))  \right]
&\geq \sum_{i=1}^2 \left[ f_1(1) - f_1(2)  \right]  \\
&= 2\left(\frac{3}{4} - \frac{1}{2}\right)
= \frac{1}{2} = f_1(2) = f_1(\text{deg}_G(v)).
\end{align*}
Hence $s(G') \geq s(G)$, and thus the claim follows by the induction hypothesis.
\EPF

\section{Improved bounds for 2-independence}
In this section we will improve the bounds for $2$-independence for graphs in
which the average degree is an integer divisible by 3. It was proven in \cite{caro1}
that a graph $G$ of order $n$ and average degree $d=3t$ for an integer $t\geq 0$ satisfies
$\alpha_2(G) \geq \frac{n}{t+1}$. In this section we improve this bound, proving the following.
\BTHM\label{improvedbound1}
Let $t > 0$ be an integer. If $G$ is a graph of order $n$ and average degree $d=3t$ then
\[
\alpha_2(G) \geq \frac{n}{t+1} \left( 1 + \frac{4}{15t^2 + 25t + 6} \right).
\]
\ETHM
\BPF
Define function the $h(x) = \dfrac{1}{x+1} \left( 1 + \dfrac{4}{15x^2 + 25x + 6} \right)$. We will prove that
$\alpha_2(G) \geq n h(t)$. 

We can assume that $n$ is divisible by $l = 15t^2 + 25t + 6$.
This assumption holds as we can build a graph $G' = l G$ (that is
$G'$ is a disjoint union of $l$ copies of $G$). Notice that $d(G) = d(G') = 3t$
and that the number of vertices $n'$ of $G'$ is divisible by $l$.
Now if $\alpha_2(G') \geq n' h(t)$ then by the pigeonhole principle the original graph $G$ satisfies
$ \alpha_2(G) \geq \frac{n'}{l} h(t) = n h(t)$.  

We define parameter $s$ as follows:
\begin{equation}\label{sdef}
s =  \frac{6 t n}{15t^2 + 25t + 6}.
\end{equation}
Notice that $s$ is an integer as $n$ is divisible by $15t^2 + 25t + 6$.
Furthermore, $s > 0$. \\
Set $G_0 = G$. If there is a vertex $v_0 \in V(G_0)$ such that
$\text{deg}_{G_0}(v_0) \geq 3t+1$, remove
it from the graph $G_0$ and call the resulting graph $G_1$ (that is $G_1 = G_0 - v_0$). 

Now if $s>1$ and there is a vertex $v_1 \in V(G_1)$ such that $\text{deg}_{G_1}(v_1) \geq 3t+1$, remove
$v_1$ from the graph $G_1$ and call the resulting graph $G_2$, that is $G_2 = G_1 - v_1$. \\
We repeat this operation iteratively. In iteration $i$ (starting with $i=0$) we first check if $i=s$ or $\Delta(G_i) \leq 3t$,
and if one of these conditions holds we terminate the process. Otherwise, we pick a vertex $v_i \in V(G_i)$ such that $\text{deg}_{G_i}(v_i) \geq 3t+1$ and remove it from the graph $G_i$. We call the resulting graph $G_{i+1}$ (that is, $G_{i+1} = G_i - v_i$). \\
Suppose that the process above terminated on iteration $j \leq s$, that is, the last graph created in the process is $G_j$. If $j<s$ then $\Delta(G_j) \leq 3t$ and thus we have
\begin{align*}
\alpha_2(G_j) &\geq (n-s) \frac{5}{5t+3} &&\text{(by Theorem \ref{threedeg_bound})} \\
&= n \frac{5}{5t+3} \left( 1 - \frac{6 t}{15t^2 + 25t + 6} \right) \\
&=  n \frac{5}{5t+3} \frac{15t^2 + 19t + 6}{15t^2 + 25t + 6} \\
&=  n \frac{5}{5t+3} \frac{(5t+3)(3t+2)}{15t^2 + 25t + 6} \\
&=  n \frac{5(3t+2)}{15t^2 + 25t + 6} \\
&= \frac{n}{t+1} \left( 1 + \frac{4}{15t^2 + 25t + 6} \right)
\end{align*}
and that is what we wanted to prove. 

The remaining case is $j=s$.
In this case $e(G_s) \leq \frac{3tn}{2} - (3t+1)s$, as in each iteration at least $3t+1$ edges were removed. Thus $d(G_s) \leq \frac{3tn - 2(3t+1)s}{n-s}$. We
shall prove this case by applying Theorem \ref{general_bound1}. Hence, because of
Lemma \ref{fkproperties}, we will assume that
\begin{equation} \label{ddef}
 d(G_s) = \frac{3tn - (6t+2)s}{n-s}.
\end{equation}
Now we shall prove that $3(t-1) < d(G_s) \leq 3t$.

\emph{Claim 1:}  $d(G_s) \leq 3t$ \\
This follows as
\[
d(G_s) = \frac{3tn - (6t+2)s}{n-s} \leq 3t.
\]

\emph{Claim 2:}  $d(G_s) > 3(t-1)$ \\
We need to prove that
\[
d(G_s) = \frac{3tn - (6t+2)s}{n-s} > 3(t-1)
\]
which is equivalent to
\begin{equation}\label{notimportant_eq1}
3tn - (6t+2)s > 3(t-1)(n-s).
\end{equation}
Now Equation \ref{notimportant_eq1} holds if and only if
\begin{equation}\label{notimportant_eq2}
3n - 5s - 3ts > 0.
\end{equation}
and Equation \ref{notimportant_eq2} holds if and only if $s < \frac{3n}{5+3t}$.
Finally, as $t>0$ in an integer, we have
\[
s =  \frac{6 t n}{15t^2 + 25t + 6} < \frac{3n}{5+3t}
\]
and thus Claim 2 follows.

We have shown that $3(t-1) < d(G_s) \leq 3t$, and hence $\lceil d(G_s)/3 \rceil = t$. \\
Now we apply Theorem \ref{general_bound1} to get
\begin{align*}
\alpha_2(G_s) &\geq f \negthinspace \left(\frac{d(G_s)}{3}\right) (n-s) \\
&= g \negthinspace \left(\frac{d(G_s)}{3}\right) (n-s) &&\text{(by Lemma \ref{mainlem1})} \\
&= \frac{n-s}{(t+1)t} \left( 2t - \frac {d(G_s)}{3} \right) \\
&= \frac{2(n-s)}{t+1} - \frac{3tn - (6t+2)s}{3t(t+1)} &&\text{(by Equation \ref{ddef})} \\
&= \frac{6t(n-s) - 3tn +(6t+2)s}{3t(t+1)} \\
&= \frac{3tn + 2s}{3t(t+1)} \\
&= \frac{n}{t+1} + \frac{2}{3t(t+1)} \frac{6tn}{15t^2 + 25t + 6} &&\text{(by Equation \ref{sdef})} \\
&= \frac{n}{t+1} \left( 1 + \frac{4}{15t^2 + 25t + 6} \right).
\end{align*}
This completes the proof.
\EPF
\BCR\label{lastcor}
If $G$ is a graph of order $n$ and average degree $d>0$ then $\alpha_2(G) > \frac{3}{d+3} n$.
\ECR
\BPF
If $\frac{d}{3}$ is not an integer then we have by Theorem \ref{general_bound1} and Lemma \ref{simplebound} that
$\alpha_2(G) > \frac{3}{d+3} n$. 

If $\frac{d}{3}$ is an integer then by Theorem \ref{improvedbound1} we have $\alpha_2(G) > \frac{3}{d+3} n$ for $d>0$,
and we are done.
\EPF
\section{Discussion}
The two most important open questions remaining are the following:
\begin{enumerate}
\item Prove Conjecture \ref{secondconj}.
\item Improve the bounds of Theorem \ref{general_bound1} for $k\geq 2$. Even an improvement of the bounds of Theorem \ref{improvedbound1} would be interesting.
\end{enumerate}
One direction of trying to prove Conjecture \ref{secondconj} would be to find a probabilistic argument, similar in spirit to that used for finding a large independent set (see \cite{noga1} page 95): there one considers a random permutation on the graph vertices, and adds a vertex $v$ to the independent set if in the permutation it precedes all its neighbors. 

As for improving the bound of Theorem \ref{improvedbound1}, one could use the
following Theorem \cite{chinese1} to gain a slight improvement for the case where the average degree is 3.
\BTHM
If $G$ is a graph of order $n$ and $\delta(G) \geq 2$, then $\gamma(G) \leq \frac{3n +|V_2|}{8}$,
 where $V_2$ denotes the set of vertices of degree $2$ in $G$.
\ETHM
This improvement is very slight (details are omitted).

\section*{Acknowledgements}
Work supported in part by the Israel Science Foundation (grant No.~1388/16).
The author thanks Uriel Feige for helpful discussions.
%This research was supported by The Israel Science Foundation (grant
%No. 263/02).

\begin{thebibliography}{JBHUL93}

\bibitem[AS08]{noga1}
Noga Alon and Joel~H. Spencer.
\newblock {\em The Probabilistic Method}.
\newblock Wiley, third edition, 2008.

\bibitem[BCHN13]{caro3}
Asen Bojilov, Yair Caro, Adriana Hansberg, and Nedyalko Nenov.
\newblock Partitions of graphs into small and large sets.
\newblock {\em Discrete Applied Mathematics}, 161(13-14):1912--1924, September
  2013.

\bibitem[Car79]{caro2}
Yair Caro.
\newblock New results on the independence number.
\newblock {\em Tech. Report, Tel-Aviv University}, 1979.

\bibitem[CH13]{caro1}
Yair Caro and Adriana Hansberg.
\newblock New approach to the $k$-independence number of a graph.
\newblock {\em Electronic Journal of Combinatorics}, 20(1):\#P33, 2013.

\bibitem[CT91]{carotuza}
Yair Caro and Zsolt Tuza.
\newblock Improved lower bounds on $k$-independence.
\newblock {\em Journal of Graph Theory}, 15(1):99--107, March 1991.

\bibitem[HL97]{magnus1}
Magnus~M. Halld\'{o}rsson and Hoong~Chuin Lau.
\newblock Low-degree graph partitioning via local search with applications to
  constraint satisfaction, max cut, and coloring.
\newblock {\em Journal of Graph Algorithms and Applications}, 1(3):49--61,
  1997.

\bibitem[HP13]{DBLP:journals/dam/HansbergP13}
Adriana Hansberg and Ryan Pepper.
\newblock On \emph{k}-domination and \emph{j}-independence in graphs.
\newblock {\em Discrete Applied Mathematics}, 161(10-11):1472--1480, 2013.

\bibitem[HS86]{hopkins1}
Glenn Hopkins and William Staton.
\newblock Vertex partition and k-small subsets of graphs.
\newblock {\em Ars Combinatoria}, 22:19--24, 1986.

\bibitem[JBHUL93]{convexbook}
Jean-Baptiste, Hiriart-Urruty, and Claude Lemar\'{e}chal.
\newblock {\em Convex Analysis and Minimization Algorithms I}.
\newblock Springer-Verlag, 1993.

\bibitem[Lov66]{lovlemma1}
L\'{a}szl\'{o} Lov\'{a}sz.
\newblock On decompositions of graphs.
\newblock {\em Studia Sci. Math Hungar.}, 1:237--238, 1966.

\bibitem[Ree96]{reed1}
Bruce Reed.
\newblock Paths, stars and the number three.
\newblock {\em Combinatorics Probability and Computing}, 5(3):277--295, 1996.

\bibitem[SSYH09]{chinese1}
Er~Fang Shan, Moo~Young Sohn, Xu~Dong Yuan, and Michael~A. Henning.
\newblock Domination number in graphs with minimum degree two.
\newblock {\em Acta Mathematica Sinica (English Series)}, 25:1253--1268, 2009.

\bibitem[Tur41]{turan}
Paul Tur\'an.
\newblock On an extremal problem in graph theory (hungarian).
\newblock {\em Math. Fiz. Lapok}, 48:436--452, 1941.

\bibitem[Wei81]{wei1}
V.~K. Wei.
\newblock A lower bound on the stability number of a simple graph.
\newblock {\em Bell Laboratories Technical Memorandum, 81-11217-9, Murray Hill,
  NJ}, 1981.

\end{thebibliography}



%\bibliographystyle{alpha}
%\bibliography{draft1}

%\begin{appendix}
%\section{Alternative proof to theorem \ref{muhahaha}}


%\end{appendix}\

\end{document}
% ------------------------------------------------------------------------
