\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
On the Modes of the Independence  \\
\vskip .1in
Polynomial of the Centipede  
}
\vskip 1cm
\large
Moussa Benoumhani\footnote{This work
is supported by the deanship of scientific research of
Al-Imam University under project number 301212.}
\\
Department of Mathematics\\
Faculty of Sciences \\
Al-Imam University\\
P. O. Box 90950 \\
Riyadh 11623 \\
Saudi Arabia\\
\href{mailto:benoumhani@yahoo.com}{\tt benoumhani@yahoo.com}
\end{center}

\vskip .2 in

\begin{abstract}
The independence polynomial of the graph called the
centipede has only real
zeros. It follows that this polynomial is log-concave, and hence unimodal.
Levit and Mandrescu gave a conjecture about the mode of this polynomial. In
this paper, the exact value of the mode is determined, and some central
limit theorems for the sequence of the coefficients are established.
\end{abstract}

\section{Introduction}

All graphs considered in this paper are assumed to be finite and
simple. The terminology is taken from \cite{D}, or may be found in any
other standard book on graph theory. A graph $G$ is denoted by $G=(E,
V)$ where $V$ is the set of its vertices and $E$ is the set of
its edges. A {\it tree\/} is a
connected, cycle-free graph. A {\it spider\/} is a tree having at most
one vertex of degree greater than 3. A {\it centipede\/} is a tree;
it is
denoted by $W_n=(A, B, E)\; n \geq 1$,
where $A \bigcup B$ is its vertex set,
$A = (a_1, \; \ldots,\;a_n)$ ; $B = (b_1,\;\ldots, b_n)$
and the edge set $E = \{ a_ib_i : 1\leq i\leq n \}\bigcup \{ b_ib_{i+1}\;: 1\leq i\leq n \}$  (see Figure \ref{fig:1} shown below). 
A {\it stable set\/} is a set of pairwise nonadjacent vertices.
The number of the stable sets having $k$ elements is denoted by $s_k$.
The {\it independence number\/} $ \alpha(G)$ of a graph $G$ is the
cardinality of a maximum independent set.
A graph is {\it well-covered\/} provided all its maximal
stable sets have the same size;
this notion was introduced by Plummer \cite{G2}. A graph is
{\it very well-covered\/} if $G$ has no isolated vertex and $|V|=2\alpha(G)$.
The independence polynomial of the graph $G$ \cite{Gut} is the
polynomial $I(G, x)=\displaystyle \sum_{k=0}^{\alpha(G)}s_{k}x^k$. The
study of these polynomials is important, since they supply many
information about the graph itself. There are many open questions
concerning these polynomials and/or  their coefficients, especially
unimodality and real zeros.  Let us recall the following notions:\\
A real positive sequence $(a_k)_{k=0}^{n}$ is said to be {\it unimodal},
if there exist integers $k_0, \; k_1,\; k_0\leq k_1$,
such that
 $$ a_0 \leq a_1\leq \cdots \leq a_{k_0} =a_{k_0+1}=\cdots=a_{k_1}\geq a_{k_1+1} \geq \cdots \geq a_n.$$ 
The integers $k_0\leq k\leq k_1$  are the {\it modes\/} of the sequence.
A sequence is {\it log-concave} if
 $\displaystyle  a_k^2\geq a_{k-1}a_{k+1},\; {\rm for} \; 1\leq k \leq n-1.$
A real sequence $(a_k)$ is said to {\it have no internal zeros} (NIZ)
if $ i<j, a_i\neq 0, \; a_j\neq 0 \; {\rm then}\; a_l \neq 0 $ for every $l, i\leq l \leq j$. A (NIZ) log-concave sequence is obviously unimodal, but the converse is not true. The sequence 1, 1, 4, 5, 4, 2,1 is unimodal but not log-concave. Note the importance of (NIZ): the sequence 0, 1, 0, 0, 2, 1 is  log-concave but not unimodal.
A real polynomial is {\it unimodal} (log-concave, symmetric, respectively) provided that the sequence of its coefficients is unimodal (log-concave, symmetric, respectively).
If the inequalities in the log-concavity definition are strict, then the  sequence is called {\it strictly log-concave} (SLC for short), and in this case, it has at most two consecutive modes.
The next result (due to Newton) may be helpful in proving unimodality:\\
If the polynomial $ \displaystyle \sum_{k=0}^{n}a_kx^k $ associated with the sequence  $(a_k)_{k=0}^{n}$ has only real zeros then
    $$ a_k^2 \geq \frac{k+1}{k}\frac{n-k+1}{n-k} a_{k-1}a_{k+1},\; {\rm for} \; 1\leq k \leq n-1.$$
If the sequence  $(a_k)_{k=0}^{n}$  is positive then it is SLC.\\ The determination of the mode rests heavily on the following result.  
\begin{theorem} [Darroch \cite{Dar}]\label{Dar} \label{thm:1.1} Let $(a_k)_{k=0}^{n}$ be a positive real sequence. Suppose that the polynomial $ \displaystyle \sum_{k=0}^{n}a_kx^k$ has only real zeros. Then  every mode of the sequence $(a_k)_{k=0}^{n}$ satisfies
\begin{equation} \left \lfloor \frac{\displaystyle \sum_{k=0}^{n}ka_k}{\displaystyle \sum_{k=0}^{n}a_k} \right \rfloor \leq k_0 \leq \left \lceil \frac{\displaystyle \sum _{k=1}^{n}ka_k}{\displaystyle \sum_{k=0}^{n} a_k} \right \rceil .\end{equation}
\end{theorem}
Darroch's result was also proved independently in \cite{3,4}.
A famous conjecture about the  unimodality of the independence polynomial of a tree,  stated by Erd\H{o}s et al.\ \cite{1} is 
\begin{conjecture} The independence polynomial of a tree is unimodal. \end{conjecture}

An important result concerning the independence polynomials of graphs is Hamidoune's  result \cite{G7}.
\begin{theorem}
The independence polynomial of a claw free graph is log-concave. \end{theorem}

Recall that a {\it claw-free graph\/} is a graph which does not contain an induced subgraph isomorphic to $K_{1,3}$. A stronger result was proved recently by Chudnovsky and Seymour \cite{ch}:

\begin{theorem}  The independence polynomial of a claw free graph has only real zeros. \end{theorem}

The centipedes are well-covered trees (see Figure \ref{fig:1}  below). The independence polynomial of the centipede is log-concave \cite{G10, G11}, in fact $I(W_n,x)$ has only real zeros and
$$ I(W_n,x)=(1+x)^ {\lfloor \frac{n}{2} \rfloor}H(x),$$
where $H(x)$ is the independence polynomial of a claw-free graph $G$, where $G \in \{ M_n, L_n\}$ (see Figure \ref{fig:2} and Figure \ref{fig:3} below). The sequence $ \displaystyle A_n=I(W_n,1)$ is known and counts the number of words of length $n$, without adjacent $0'$s from the alphabet $\{0,1,2\}$. This is sequence \seqnum{A028859} in Sloane's online Encyclopedia. 
The unimodality of the polynomial $I(W_n,x)$ was proved by Levit and Mandrescu \cite{G1}. There it was conjectured that the mode $k_n$ of $I_n(W, x)$ is
\begin{eqnarray*}
k_n&=&n-f(n) \\
f(n) &=& \begin{cases}
1 + \left \lfloor \frac{n}{5} \right \rfloor, & \text{if $2 \leq n \leq  6$;} \\
f \left(2 + ((n-2) \text{ mod } 5) \right) + 2 \left \lfloor \frac{n-2}{5} \right \rfloor, &
\text{if $n\geq 7$}. 
\end{cases}
\end{eqnarray*}
Wang and Zhu \cite {WZ} proved that the zeros of $I_n(W, x)$ are real;
they also determine the zeros explicitly.
Using this fact, and  Darroch's result, 
\cite {Dar}, they gave a counterexample for $n=142$,
by showing that $k_{142}=85,$ as stated by the conjecture,
is not a mode of $I_n(W, x)$.  

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{.5cm}
\begin{picture}(15,5)
\put(0,0){\circle*{.5}}
\put(0,3){\circle*{.5}}
\put(3,0){\circle*{.5}}
\put(3,3){\circle*{.5}}
\put(6,0){\circle*{.5}}
\put(6,3){\circle*{.5}}
\put(0,-.9){$a_1$}
\put(0,3.5){$b_1$}
\put(3,-.9){$a_2$}
\put(3,3.5){$b_2$}
\put(6,-.9){$a_3$}
\put(6,3.5){$b_3$}
\put(12,-.9){$a_n$}
\put(12,3.5){$b_n$}
\put(0,0){\line(0,1){3}}
\put(3,0){\line(0,1){3}}
\put(6,0){\line(0,1){3}}
\put(12,0){\circle*{.5}}
\put(0,0){ \line(1,0){3}}
\put(3,0){\line(1,0){3}}
\put(12,0){\line(0,1){3}}
\put (12,3) {\circle*{.5}}
\put(6,0){..........................}
\end{picture} 
\end{center}
\caption{ The centipede $W_n$ }\label{fig:1}
\end{figure}
In this paper, using Theorems \ref{thm:1.1} and \ref{thm:2.1},
we estimate, up to an additive factor of $1$,
the mode of the polynomial $I(W_n,x)$.
We evaluate $ I'(W_n,1)/I(W_n,1)$. The explicit form of the polynomial
given by Wang and Zhu is explicit, but not suitable for our
calculations. We use the reciprocal polynomial of $H(x)$, making the
manipulation of $I'(W_n,1)$ and $I(W_n,1)$ easier. Finally, we prove
that the sequence $s_k$ is asymptotically normal.

\section{ The independence polynomial of the centipede}
Wang and  Zhu \cite{WZ} proved  that $I(W_n,x)$ has only real zeros. 
Although in their result the zeros are given explicitly,
for our purposes, we will need a closed form that
will enable us to evaluate
$\displaystyle \left  \lfloor \frac{I'(W_n,1)}{I(W_n,1)} \right \rfloor $.
The  independence polynomial $I(W_n,x)$ satisfies the recursion \cite{G10, G11, G1}
\begin{equation} I(W_n,x)=(x+1) \left (I(W_{n-1},x)+xI(W_{n-2},x) \right ),\end{equation}
with $ W_0=1,\; I(W_1,x)=1+2x$. 
 \begin{theorem} \cite{WZ}\label{thm:2.1}
The independence polynomial of the centipede is given by
\begin{eqnarray*} I(W_n,x)&=& \frac{(x+1)^{\left \lfloor\frac{n}{2}\right \rfloor}}{\sqrt{\Delta}} \left ( \left ( \frac{3x+1+\sqrt{\Delta} }{2}  \right )^{\frac{n+2}{2}}-
    \left ( \frac{3x+1-\sqrt{\Delta} }{2}    \right )^{\frac{n+2}{2}} \right ) \\
    &=& (x+1)^{\left \lfloor\frac{n}{2}\right \rfloor}H(x),
 \end{eqnarray*}
where $\Delta=5x^2+6x+1.$
 \end{theorem}
 \begin{proof}
By  \cite[Lemma 2.3]{WZ}, we have  
$$ I(W_n,x)=\frac{1}{(x+1)\sqrt{\Delta}} \left ( \left ( \frac{1+x+\sqrt{\Delta}}{2} \right )^{n+2}- \left (\frac{x+1-\sqrt{\Delta}}{2}\right )^{n+2} \right ).$$
The last formula is explicit but not convenient for calculations, especially for  the localization the mode of the polynomial $I(W_n,x)$.  A  more explicit one is given below. 
Let  $n=2l$. Then 
$$I(W_{2l},x) = $$
\begin{eqnarray*}
&& \frac{1}{(x+1)\sqrt{\Delta}} \left ( \left ( \frac{1+x+\sqrt{\Delta}}{2} \right )^{2l+2}- \left (\frac{x+1-\sqrt{\Delta}}{2}\right )^{2l+2} \right )\\
&=& \frac{1}{(x+1)\sqrt{\Delta}} \left ( \left (  \left (\frac{1+x+\sqrt{\Delta}}{2} \right )^{2} \right )^{l+1}-
    \left ( \left ( \frac{x+1-\sqrt{\Delta}}{2}\right )^{2} \right )^{l+1} \right ) \\
&=& \frac{1}{(x+1)\sqrt{\Delta}} \left ( \left ( \frac{6x^2+8x+2+2(x+1)\sqrt{\Delta} }{4}  \right )^{l+1}-
    \left ( \frac{6x^2+8x++2-2(x+1)\sqrt{\Delta} }{4}    \right )^{l+1} \right ) \\
&=& \frac{1}{(x+1)\sqrt{\Delta}} \left ( \left ( \frac{3x^2+4x+1+(x+1)\sqrt{\Delta} }{2}  \right )^{l+1}-
    \left ( \frac{3x^2+4x+1-(x+1)\sqrt{\Delta} }{2}    \right )^{l+1} \right )\\
&=& \frac{(x+1)^{l}}{\sqrt{\Delta}} \left ( \left ( \frac{3x+1+\sqrt{\Delta} }{2}  \right )^{l+1}-
    \left ( \frac{3x+1-\sqrt{\Delta} }{2}    \right )^{l+1} \right ) \\
&=&(x+1)^{l}H_{l}(x)
 \end{eqnarray*}
 For $n=2l+1$, ($j=l+1$) we have
$$ I(W_{2l+1},x) = $$
 \begin{eqnarray*}
&& \frac{1}{(x+1)\sqrt{\Delta}} \left ( \left ( \frac{1+x+\sqrt{\Delta}}{2} \right )^{2l+3}- \left (\frac{x+1-\sqrt{\Delta}}{2}\right )^{2l+3} \right )\\
&=& \frac{1}{(x+1)\sqrt{\Delta}} \left (  \left ( \frac{1+x+\sqrt{\Delta}}{2} \right ) \left (  \left (\frac{1+x+\sqrt{\Delta}}{2} \right )^{2} \right )^{j}-
   \left ( \frac{x+1-\sqrt{\Delta}}{2}\right ) \left ( \left ( \frac{x+1-\sqrt{\Delta}}{2}\right )^{2} \right )^{j}  \right ) \\
&=&  \frac{(x+1)^{j-1}}{\sqrt{\Delta}} \left (  \left ( \frac{1+x+\sqrt{\Delta}}{2} \right ) \left ( \frac{3x+1+\sqrt{\Delta}}{2}  \right )^{j}-
   \left ( \frac{x+1-\sqrt{\Delta}}{2}\right ) \left (  \frac{3x+1-\sqrt{\Delta}}{2} \right )^{j}  \right )\\
&=& \frac{(x+1)^{j-1}}{\sqrt{\Delta}} \left (   \left ( \frac{3x+1+\sqrt{\Delta}}{2}  \right )^{j+\frac{1}{2}}-
    \left (  \frac{3x+1-\sqrt{\Delta}}{2} \right )^{j+\frac{1}{2}}  \right )\\
   &=&\frac{(x+1)^{l}}{\sqrt{\Delta}}    \left (   \left ( \frac{3x+1+\sqrt{\Delta}}{2}  \right )^{\frac{2l+3}{2}}-  \left (  \frac{3x+1-\sqrt{\Delta}}{2} \right )^{\frac{2l+3}{2}}     \right ) \\
&=&(x+1)^{l}H_{l+1}(x)
 \end{eqnarray*}
Gathering all this together, we obtain the desired formula:
\begin{equation}
I(W_n,x)=\frac{(x+1)^{\left \lfloor\frac{n}{2}\right \rfloor}}{\sqrt{\Delta}} \left ( \left ( \frac{3x+1+\sqrt{\Delta} }{2}  \right )^{\frac{n+2}{2}}-
    \left ( \frac{3x+1-\sqrt{\Delta} }{2}    \right )^{\frac{n+2}{2}} \right )=(x+1)^{\lfloor \frac{n}{2} \rfloor}H(x)
 \end{equation}
 \end {proof}
The polynomial $H(x)$ is of degree $ \lfloor \frac{n+1}{2}\rfloor$. Also, these polynomials are the independence polynomials of the claw-free graphs $M_n$ (if $n$ is even,  and $L_n$ (if $n$ is odd). The fact that the polynomial $I(W_n,x)$ has only real zeros, follows from the general result of  Chudnovsky and  Seymour\cite{ch}. 
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{.5cm}
\begin{picture}(20,6)
\put(0,0){\circle*{.5}}
\put(3,0){\circle*{.5}}
\put(1.5, 3){\circle*{.5}}
\put(6,0){\circle*{.5}}
\put(7.5,3){\circle*{.5}}
\put(1.5,3){\line(1,-2){1.5}}
\put(9,0){\circle*{.5}}
\put(0,0){\line(1,2){1.5}}
\put(0,0){\line(1,2){1.5}}
\put(12,0){\line(1,2){1.5}}
\put(13.5,3){\line(1,-2){1.5}}
\put(12,0){\line(1,0){3}}
\put(12,0){\circle*{.5}}
\put(0,0){ \line(1,0){3}}
\put(3,0){\line(3,0){3}}
\put (13.5,3) {\circle*{.5}}
\put(15,0){\circle*{.5}}
\put(6,0){\line(1,2){1.5}}
\put(6,0){\line(1,0){3}}
\put(7.5,3){\line(1,-2){1.5}}
\put(9,0){.............}
\end{picture}
\end{center}
\caption{ The graph $L_n$ }\label{fig:2}
\end{figure}
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{.5cm}
\begin{picture}(20,6)
\put(0,0){\circle*{.5}}
\put(3,0){\circle*{.5}}
\put(1.5, 3){\circle*{.5}}
\put(6,0){\circle*{.5}}
\put(7.5,3){\circle*{.5}}
\put(1.5,3){\line(1,-2){1.5}}
\put(9,0){\circle*{.5}}
\put(0,0){\line(1,2){1.5}}
\put(0,0){\line(1,2){1.5}}
\put(12,0){\line(1,2){1.5}}
\put(13.5,3){\line(1,-2){1.5}}
\put(12,0){\line(1,0){3}}
\put(12,0){\circle*{.5}}
\put(0,0){ \line(1,0){3}}
\put(3,0){\line(3,0){3}}
\put (13.5,3) {\circle*{.5}}
\put(15,0){\circle*{.5}}
\put(15,0){\line(1,0){3}}
\put(6,0){\line(1,2){1.5}}
\put(6,0){\line(1,0){3}}
\put(7.5,3){\line(1,-2){1.5}}
\put(9,0){.............}
\put(18,0){\circle*{.5}}
\put(18,0){\line(0,1){3}}
\put(18,3){\circle*{.5}}

\end{picture}
\end{center}
\caption{ The graph $M_n$ }\label{fig:3}
\end{figure}
Now we can determine the mode of the centipede.
 \begin{theorem}
Every mode of the independence polynomial of the centipede satisfies
 $$  \left \lfloor n-\frac{1}{2}  \left \lfloor \frac{n}{2} \right \rfloor-\frac{\sqrt{3}}{12}(n+2)+\frac{1}{3} \right \rfloor \leq k_0 \leq  \left \lfloor n-\frac{1}{2}  \left \lfloor \frac{n}{2} \right \rfloor-\frac{\sqrt{3}}{12}(n+2)+\frac{1}{3} \right \rfloor+1 .$$
 \end{theorem}
 \begin{proof}
Our aim is to evaluate $\displaystyle \frac{I'(W_n,1)}{I(W_n,1)}.$ We just need to evaluate  $H'(x)$. Unfortunately, it turns out that $H'(x)$ is not easy to handle, and then, the form of  $\frac{H'(1)}{H(1)}$ is also cumbersome.\\
In order to avoid this, consider the reciprocal polynomial:
 \begin{eqnarray*}
 H_r(x)&=&x^{\lfloor \frac{n+1}{2}\rfloor} H(\frac{1}{x})\\
    &=& \frac{1}{\sqrt{B}} \left ( \left ( \frac{x+3+\sqrt{B} }{2}  \right )^{\frac{n+2}{2}}-
    \left ( \frac{x+3-\sqrt{B} }{2}    \right )^{\frac{n+2}{2}} \right ),
 \end{eqnarray*}

where $B=x^2+6x+5$. Now
\begin{equation*}
H_r{'}(x)=\frac{(n+2)}{2B} \left ( \left ( \frac{x+3+\sqrt{B} }{2}  \right )^{\frac{n+2}{2}}+
    \left ( \frac{x+3-\sqrt{B} }{2}    \right )^{\frac{n+2}{2}} \right )-\frac{(x+3)}{B}H_r(x).
     \end{equation*}

Note that $$ \frac{I'(W_n,1)}{I(W_n,1)}=\frac{1}{2}  \left \lfloor \frac{n}{2} \right \rfloor+\frac{H'(1)}{H(1)}.$$
But $$ \frac{H'(1)}{H(1)}= \left \lfloor \frac{n+1}{2} \right \rfloor- \frac {H'_r(1)}{H_r(1)},$$
now
\begin{eqnarray*}
\frac { H_r'(1) }{H_r(1)}&=& \sqrt{3} \frac{(n+2)}{12}\frac{1+a^{n+2}}{1-a^{n+2}}-\frac{1}{3},\qquad (a=7-4 \sqrt{3}=0.07179 \cdots)\\
&\geq& \sqrt{3} \frac{(n+2)}{12}- \frac{1}{3}.
\end{eqnarray*}
On the other hand, 
$$
\frac {H_r'(1)}{H_r(1)} <  \sqrt{3} \frac{(n+2)}{12}-\frac{1}{3}+\frac{2}{3}
$$
is equivalent to 
$$ \sqrt{3}\frac{(n+2)}{12}\frac{1+a^{n+2}}{1-a^{n+2}} \leq \sqrt{3} \frac{(n+2)}{12}+\frac{2}{3},$$ or 
$$ \frac{(n+2)a^{n+2}}{1-a^{n+2}} \leq \frac{4}{\sqrt{3}},$$
which is true, since  the function $ \displaystyle x(e^{\alpha x}-1)^{-1}, \; \alpha> 0,$ is decreasing for $x \geq 1$.
So,
\begin{eqnarray*}
 \frac{I'(W_n,1)}{I(W_n,1)}&=& \frac{1}{2}  \left \lfloor \frac{n}{2} \right \rfloor+\frac{H'(1)}{H(1)}\\
  &=& \frac{1}{2}  \left \lfloor \frac{n}{2} \right \rfloor+\left \lfloor \frac{n+1}{2} \right \rfloor- \frac {H'_r(1)}{H_r(1)} \\
  &\leq & n-\frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor - \frac {H'_r(1)}{H_r(1)}\leq n-\frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor - \sqrt{3} \frac{(n+2)}{12}+ \frac{1}{3}.
  \end{eqnarray*}
 We obtain
 \begin{equation} \left  \lfloor \frac{I'(W_n,1)}{I(W_n,1)}\right \rfloor \leq
 \left \lfloor  n-\frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor - \sqrt{3} \frac{(n+2)}{12}+ \frac{1}{3} \right \rfloor  \label{2.3}.\end{equation}
Also
\begin{eqnarray*}
 \frac{I'(W_n,1)}{I(W_n,1)}&=& \frac{1}{2}  \left \lfloor \frac{n}{2} \right \rfloor+\frac{H'(1)}{H(1)}\\
  &=& \frac{1}{2}  \left \lfloor \frac{n}{2} \right \rfloor+\left \lfloor \frac{n+1}{2} \right \rfloor- \frac {H'_r(1)}{H_r(1)} \\
  &\geq & n-\frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor - \frac {H'_r(1)}{H_r(1)}\geq n-\frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor - \sqrt{3} \frac{(n+2)}{12}+ \frac{1}{3}-\frac{2}{3}\\
  &>&n-\frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor - \sqrt{3} \frac{(n+2)}{12}+ \frac{1}{3}-1.
  \end{eqnarray*}
  It follows then that
    \begin{equation} \left  \lfloor \frac{I'(W_n,1)}{I(W_n,1)} \right \rfloor \geq \left \lfloor  n-\frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor - \sqrt{3} \frac{(n+2)}{12}+ \frac{1}{3} \right \rfloor-1 \label{2.4}.\end{equation}
    Equations (\ref{2.3}) and (\ref{2.4}) give the desired result. \end{proof}
   \begin{corollary} For every $ l \in \mathbb{N}, \; l\geq 1$, there exists an integer $n_0$ such that
    $$\frac{I'(W_n,1)}{I(W_n,1)}-k_n>l,\;for \; n\geq n_0.$$ In other words, the conjecture of Levit and Mandrescu is false.
    \end{corollary}
    \begin{proof} Let $ l>0$, be a fixed integer. Then
    \begin{equation*}
    \frac{I'(W_n,1)}{I(W_n,1)} \geq n-\frac{1}{2} \left \lfloor \frac{n}{2} \right \rfloor - \sqrt{3} \frac{(n+2)}{12}+ \frac{1}{3}-\frac{2}{3}\\
      \geq  \frac{(9- \sqrt{3})}{12}n-1.
     \end{equation*}
Also
$$k_n  \leq  \frac{3}{5}n+3 .$$
But for $ n \geq 801$, say, we have
$$\frac{I'(W_n,1)}{I(W_n,1)}-k_ n \geq \frac{(9- \sqrt{3})}{12}n-\frac{3}{5}n-4 \geq  .0005 n-4>0,$$
and then, for $ n \geq 200(l+4)$ we obtain the desired result.
    \end {proof}
The calculations agove are not very accurate, and $ n \geq 800 $ may be highly improved. For example, for $n=202$ we have
  $$\frac{I'(W_{402},1)}{I(W_{402},1)}-k_{402}=243.5209\cdots-241=2.5209 \cdots$$
  For $n=1000$,
$$\frac{I'(W_{1000},1)}{I(W_{1000},1)}-k_{1000}=605.707\cdots-600=5.707 \cdots$$
The constant term in  $H_r(x)$ is $F_n$, the Fibonacci number. Using the results of \cite{WZ}, we may deduce some identities involving the roots and the coefficients of the polynomials of $H(x)$. For example, the sequence of the coefficient of $x$ (=sum of the roots) in $H_r(x)$ is the sequence \seqnum{A129722}.
 Also, we may deduce 
$$ \displaystyle  \prod_{k=1}^{ \left \lfloor \frac{n+1}{2} \right \rfloor} \left ( 1+4 \cos^2 \left ( \frac{k \pi}{n+2} \right ) \right)=F_{n+1}.$$

\section{ The sequence $s_k$ is asymptotically normal}

A positive real sequence $a(n,k)_{k=0}^n,$ with $A_n=\sum
\limits_{k=0}^na(n,k)\neq 0,$ is said to satisfy a central limit theorem
(or is {\it asymptotically normal}) with mean $\mu _n$ and variance $\sigma _n^2$
if
\begin{equation}
\lim_{n\longrightarrow +\infty }\sup_{x\in R}\left| \sum\limits_{0\leq k\leq
\mu _n+x\sigma _n}\frac{a(n,k)}{A_n}-(2\pi )^{-1/2}\int\limits_{-\infty
}^xe^{-\frac{t^2}2}dt\right| =0  \label{3.1}.
\end{equation}
The sequence satisfies a local limit theorem on $B\subseteq \mathbb{R}$ ; with mean $
\mu _n$ and variance $\sigma _n^2$ if
\begin{equation}
\lim_{n\longrightarrow +\infty }\sup_{x\in B}\left| \frac{\sigma _na(n,\mu
_n+x\sigma _n)}{A_n}-(2\pi )^{-1/2}e^{-\frac{x^2}2}\right| =0 \label{3.2} .
\end{equation}
Recall the following result (see Bender \cite{2}).
\begin{theorem} \label{thm:3.1}
Let $(Q_n)_{n\geq 1}$ be a sequence of real polynomials; with only real
negative zeros. The sequence of the coefficients of the $(Q_n)_{n\geq 1}$
satisfies a central limit theorem; with $\mu _n=\frac{Q_n^{'}(1)}{Q_n(1)}$
and $\displaystyle \sigma _n^2=\left( \frac{Q_{n}^{''}(1)}{Q_n(1)}+
\frac{Q_n^{'}(1)}{Q_n(1)}-\left( \frac{Q_n^{' }(1)}{Q_n(1)}\right) ^2\right) $
provided that $\lim\limits_{n\longrightarrow +\infty }\sigma _n^2=+\infty .$
If, in addition, the sequence of the coefficients of each $Q_n$ is with no
internal zeros; then the sequence of the coefficients satisfies a local
limit theorem on $\mathbb{R}$.
\end{theorem}
Generally speaking, a central limit theorem for a sequence of random variables gives (\ref{3.1}). Relation (\ref{3.2}) is then deduced 
under the condition that the sequence has no internal zeros (see \cite{2}). Relation (\ref{3.1}) is nothing than pointwise convergence.
We have the following result
\begin{theorem}
The sequence $s_k$ satisfies a central limit and a local limit theorem
on $\mathbb{R}$, with mean $$\displaystyle \mu _n=\frac{I'(W_n,1)}{I(W_n,1)}\approx \frac{(9-\sqrt{3})n}{12}$$ and variance
$$\displaystyle \sigma _n^2 = \left( \frac{I''(W_n,1)}{I(W_n,1)}+\frac{I'(W_n,1)}{I(W_n,1)}-\left( \frac{I'(W_n,1)}{I(W_n,1)}\right) ^2\right) \approx \frac{(15-2\sqrt{3})n}{24}. $$
\end{theorem}
\begin{proof}
In order to prove that the sequence of the coefficients of $P_n(x)$ is asymptotically normal, let us evaluate
$$\left( \frac{I''(W_n,1)}{I(W_n,1)}+\frac{I'(W_n,1)}{I(W_n,1)}-\left( \frac{I'(W_n,1)}{I(W_n,1)}\right) ^2\right). $$
We have
\begin{eqnarray*}
I(W_n,x)&=& (x+1)^{\lfloor \frac{n}{2} \rfloor}H(x) \\
I'(W_n,x)&=& \left \lfloor \frac{n}{2} \right \rfloor (x+1)^{\lfloor \frac{n}{2} \rfloor-1}H(x)+ (x+1)^{\lfloor \frac{n}{2} \rfloor}H^{'}(x)\\
I''(W_n,x)&=& \left \lfloor \frac{n}{2} \right \rfloor \left ( \left \lfloor \frac{n}{2} \right \rfloor -1\right ) (x+1)^{\lfloor \frac{n}{2}\rfloor-2}H(x)+ 2\left \lfloor \frac{n}{2} \right \rfloor (x+1)^{\lfloor \frac{n}{2} \rfloor-1}H^{'}(x)+(x+1)^{\lfloor \frac{n}{2} \rfloor}H^{''}(x).
\end{eqnarray*}
We also have
$$  \frac{I'(W_n,1)}{I(W_n,1)}=\frac{\left \lfloor \frac{n}{2} \right \rfloor \left ( \left \lfloor \frac{n}{2} \right \rfloor -1\right )}{4}+   \left \lfloor \frac{n}{2} \right \rfloor \frac{H^{'}(1)}{H(1)}+\frac{H^{''}(1)}{H(1)},$$ so
\begin{eqnarray*}
 \sigma _n^2&=& \frac{\left \lfloor \frac{n}{2} \right \rfloor}{4}+\frac{H"(1)}{H(1)} +\frac{H'(1)}{H(1)}- \left ( \frac{H'(1)}{H(1)} \right )^2 \\
             &=& \frac{\left \lfloor \frac{n}{2} \right \rfloor}{4}+(\sigma _n^{H})^2 \\
&=& \frac{\left \lfloor \frac{n}{2} \right \rfloor}{4}+\frac{H'(1)}{H(1)} \left ( 1+\frac{H''(1)}{H'(1)}-\frac{H'(1)}{H(1)} \right )>\frac{\left \lfloor \frac{n}{2} \right \rfloor}{4}.
\end{eqnarray*}
It follows that $ \displaystyle \lim _{n\longrightarrow \infty} \sigma _n=\infty$, and then the sequences $s_k$ satisfies a central limit theorem.
Now let $(-\alpha_i),\; (-\beta_i)$, be respectively  the zeros of $H(x)$ and $H^{'}(x)$. Then by Rolle's theorem we get
  $$-\alpha_1 \leq \beta_1 \leq  -\alpha_2 \leq  \beta_2 \leq \;\cdots \leq -\beta_{\left \lfloor \frac{n+1}{2} \right \rfloor-1} \leq  -\alpha_{\left \lfloor \frac{n+1}{2} \right \rfloor}.$$
 We deduce
 \begin{eqnarray*}
  \left ( 1+\frac{H''(1)}{H'(1)}-\frac{H'(1)}{H(1)} \right )&=& \sum_{i=1}^{\left \lfloor \frac{n+1}{2} \right \rfloor}\frac{\alpha_i}{1+\alpha_i}- \sum_{i=1}^{\left \lfloor \frac{n+1}{2} \right \rfloor-1}\frac{\beta_i}{1+\beta_i}, \\
  &=&\frac {H'_r(1)}{H_r(1)}-\frac {H''_r(1)}{H'_r(1)} \approx 1 \end{eqnarray*}
It follows that $$ \sigma_n^{2} \approx  \frac{(15-2\sqrt{3})n}{24}$$
\end{proof}
By Theorem \ref{thm:3.1}, and because all the $s_k$ are nonvanishing,  we have a local limit theorem, from which we deduce the
\begin{corollary} Let $S_{k_0}=\max_{k}{ s_k}.$ Then we have the approximation of the maximum stable set
$$ S_{k_0} \approx  \frac{I(W_n,1)}{\sigma_n} \approx 1.02\frac{(1+\sqrt{3})^{n}}  {\sqrt {\pi n}}$$ \end{corollary}
Finally, we note that the same limit theorems, remain true for the sequences of the coefficients of the independence  polynomials of $M_n$ and $L_n$.

 \section{ Acknowledgments}
My sincere thanks to my colleague Dr.\ Ali Faryad, for his kind help in Latex drawing, as well as for the anonymous referees who have made several corrections and suggestions, which improved the style of the paper. 

\begin{thebibliography}{10}
\bibitem {1} Y. Alavi, P. J. Malde, A. J. Schwenk, and P. Erd\H{o}s,
The vertex independence sequence
of a graph is not constrained, {\it Congr. Numer.} {\bf 58} (1987), 15--23.

\bibitem{2}  E. A. Bender, Central and local limit theorems applied to
asymptotic enumeration, {\it J. Combin. Theory Ser.}  A {\bf 15}
(1973), 91--111.

\bibitem{3} M. Benoumhani,  Polyn\^{o}mes \`{a} racines r\'eelles n\'{e}gatives et applications combinatoires. Ph.\ D. Thesis,
Claude Bernard University, Lyon, France, 1993.

\bibitem {4} M. Benoumhani, Sur une propri\'{e}t\'{e} des polyn\^{o}mes
\`{a} racines r\'eelles n\'{e}gatives, {\it J. Math. Pures Appl.}
(1996), 85--110.

\bibitem {c} C. Berge, Some common properties for regularizable graphs,
edge-critical graphs and B-graphs, {\it Ann. Discrete Math.} {\bf 12}
(1982), 31--44.

\bibitem {D} J. A. Bondy and S. R.  Murty, {\it Graph Theory and
Applications}, Elsevier, 1982.

\bibitem {F}  F.  Brenti, Log-concave, unimodal  sequences in algebra,
combinatorics, and geometry, {\it Contemp. Math} {\bf 178} (1994),
71--89.

\bibitem{G4} V. Chvatal and P. J. Slater, A note on well-covered graphs,
{\it Ann. Discrete Math.}, 55 (1993), 179--182.

\bibitem {ch}  M. Chudnovsky and P. Seymour, The roots of the
independence polynomial of a clawfree graph, {\it J. Combin. Theory
Ser. B} {\bf 97} (2007), 350--357.

\bibitem{Dar} J. N. Darroch, On the distribution of the number of
successes in independent trials, {\it Ann. Math. Stat.} {\bf 35}
(1964), 1317--1321.

\bibitem{durt} R. Durrett, {\it Probability:  Theory and Examples},
Duxbury Press, 1994.

\bibitem{G5}A. Finbow, B. Hartnell, and R. J. Nowakowski, Well dominated
 graphs: a collection of well-covered ones, {\it  Ars Combin.} {\bf 25}
 (1988), 5--10.

\bibitem{Gut} I. Gutman and F. Harary, Generalizations of the matching
 polynomial, {\it Util. Math.} 24 (1983), 97-106.

\bibitem{G6} A. Finbow, B. Hartnell, and R. J. Nowakowski, A
characterization of  well covered graphs which contain neither
4- nor 5-cycles, {\it J. Graph Theory} {\bf
18} (1994), 713--721.

\bibitem{G7} Y. O. Hamidoune, On the number of the independent $k$-sets
in a claw free graph, {\it J. Combin. Theory Ser. B} {\bf 50} (1990),
241--244.

\bibitem{G8} E. L.  C. King, Characterising a subclass  of well-covered graphs, {\it Congr. Numer.} {\bf 160} (2003), 7--31.

\bibitem{G9} V. E. Levit and  E. Mandrescu, Well-covered trees,
{\it Congr. Numer.} {\bf 139} (1999), 101--112.

\bibitem{G10} V. E. Levit and E. Mandrescu, On well-covered trees with
unimodal independence polynomials,
{\it Congr. Numer.} {\bf 159} (2002) 193--202.

\bibitem{G11} V. E. Levit and E. Mandrescu, On unimodality of  independence
polynomials of some well-covered trees, in Cristian S. Calude, Michael
J. Dinneen and Vincent Vajnovszki, eds., {\it Proc. DMTCS 2003:
Proceedings of the 4th International Conference on Discrete Mathematics
and Theoretical Computer Science} LNCS Vol.\ 2731, Springer Verlag,
2003, pp.\ 237--256.

\bibitem{G1} V. E. Levit and E. Mandrescu,  Independence polynomial of
a graph--a survey. In
S. Bozapalidis, A. Kalampakas, and G. Rahonis, eds.,
{\it  Proceedings of the 1st International
Conference on Algebraic Informatics}, 2005, pp.\ 233-254. 

\bibitem{G2} D. M. Plummer,  Some covering concepts in graphs,  {\it J.
Combin. Theory Ser. B}, {\bf 8} (1970), 91--98.

\bibitem{G3} D. M. Plummer, Well-covered graphs: a survey, {\it Quaestiones
Math.} {\bf 16} (1993),  253--287.

\bibitem{SL1} N. J. A. Sloane, The Encyclopedia of Integer Sequences.
Published electronically
 at \href{http://oeis.org}{http://oeis.org}, 2011.

\bibitem{WZ} Y. Wang and B.-X. Zhu, On unimodality of  independence
polynomials of some graphs, {\it European J. Combin.} {\bf 32} (2011),
10--20.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 11B75.

\noindent \emph{Keywords: } 
Independence polynomial, centipede, log-concave sequence, limit theorem,
polynomial with real zeros, unimodal sequence, Fibonacci number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000032},
\seqnum{A000045},
\seqnum{A028859},
\seqnum{A129722}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 21 2011;
revised version received April 14 2012. 
Published in {\it Journal of Integer Sequences}, April 20 2012.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}