On the Modes of the Independence Polynomial of the Centipede

Moussa Benoumhani^{1} Department of Mathematics Faculty of Sciences Al-Imam University P. O. Box 90950 Riyadh 11623 Saudi Arabia

                     benoumhani@yahoo.com

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.

1 Introduction

All graphs considered in this paper are assumed to be finite and simple. The terminology is taken from [6], 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 tree is a connected, cycle-free graph. A spider is a tree having at most one vertex of degree greater than 3. A centipede is a tree; it is denoted by W_{n} = (A, B, E) n ≥ 1, where A ⋃ B is its vertex set, A = (a_{1}, …, a_{n}) ; B = (b_{1}, …, b_{n}) and the edge set E = {a_{i}b_{i} : 1 ≤ i ≤ n} ⋃{b_{i}b_{i+1} : 1 ≤ i ≤ n} (see Figure 1 shown below). A stable set is a set of pairwise nonadjacent vertices. The number of the stable sets having k elements is denoted by s_{k}. The independence number α(G) of a graph G is the cardinality of a maximum independent set. A graph is well-covered provided all its maximal stable sets have the same size; this notion was introduced by Plummer [21]. A graph is very well-covered if G has no isolated vertex and |V | = 2α(G). The independence polynomial of the graph G [13] is

1This work is supported by the deanship of scientific research of Al-Imam University under project number 301212.

the polynomial I(G, x) = ∑_{k=0}^{α(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 unimodal, if there exist integers k_{0}, k_{1}, k_{0} ≤ k_{1}, such that

a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{k_{0}} = a_{k_{0}+1} = ⋯ = a_{k_{1}} ≥ a_{k_{1}+1} ≥ ⋯ ≥ a_{n}.

The integers k_{0} ≤ k ≤ k_{1} are the modes of the sequence. A sequence is log-concave if a_{k}^{2} ≥ a_{k−1}a_{k+1}, for 1 ≤ k ≤ n − 1. A real sequence (a_{k}) is said to have no internal zeros (NIZ) if i < j, a_{i} ≠ 0, a_{j} ≠ 0 then a_{l} ≠ 0 for every l, i ≤ l ≤ 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 unimodal (log-concave, symmetric, respectively) provided that the sequence of its coefficients is unimodal (logconcave, symmetric, respectively). If the inequalities in the log-concavity definition are strict, then the sequence is called 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 ∑_{k=0}^{n} a_{k}x^{k} associated with the sequence (a_{k})_{k=0}^{n} has only real zeros then

a_{k}^{2} ≥ \frac{k + 1}{k} \frac{n − k + 1}{n − k}a_{k−1}a_{k+1}, for 1 ≤ k ≤ 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.

Theorem 1 (Darroch [10]). Let (a_{k})_{k=0}^{n} be a positive real sequence. Suppose that the poly-

nomial ∑_{k=0}^{n} a_{k}x^{k} has only real zeros. Then every mode of the sequence (a_{k})_{k=0}^{n} satisfies

⌊\frac{∑_{k=0}^{n} ka_{k}}{∑_{k=0}^{n} a_{k}} ⌋ ≤ k_{0} ≤ ⌈\frac{∑_{k=1}^{n} ka_{k}}{∑_{k=0}^{n} a_{k}} ⌉ .  (1)

Darroch’s result was also proved independently in [3, 4]. A famous conjecture about the unimodality of the independence polynomial of a tree, stated by Erdős et al. [1] is

Conjecture 2. The independence polynomial of a tree is unimodal.

An important result concerning the independence polynomials of graphs is Hamidoune’s result [15].

Theorem 3. The independence polynomial of a claw free graph is log-concave.

Recall that a 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 [9]:

Theorem 4. The independence polynomial of a claw free graph has only real zeros.

The centipedes are well-covered trees (see Figure 1 below). The independence polynomial of the centipede is log-concave [18, 19], in fact I(W_{n}, x) has only real zeros and

I(W_{n}, x) = (1 + x)^{⌊ \frac{n}{2} ⌋}H(x),

where H(x) is the independence polynomial of a claw-free graph G, where G ∈ {M_{n}, L_{n}} (see Figure 2 and Figure 3 below). The sequence 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 \underline{A028859} in Sloane’s online Encyclopedia. The unimodality of the polynomial I(W_{n}, x) was proved by Levit and Mandrescu [20]. There it was conjectured that the mode k_{n} of I_{n}(W, x) is

k_{n} = n − f(n)
f(n) = \begin{cases}1 + ⌊\frac{n}{5}⌋ , & if 2 ≤ n ≤ 6; \\ f (2 + ((n − 2) mod 5)) + 2 ⌊\frac{n−2}{5}⌋ , & if n ≥ 7. \end{cases}

Wang and Zhu [24] proved that the zeros of I_{n}(W, x) are real; they also determine the zeros explicitly. Using this fact, and Darroch’s result, [10], 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).

[figure: a_{1}; b_{1}; a_{2}; b_{2}; a_{3}; b_{3}; a_{n}; b_{n}; ..........................]

Figure 1: The centipede W_{n}

In this paper, using Theorems 1 and 5, 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.

2 The independence polynomial of the centipede

Wang and Zhu [24] 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 ⌊\frac{I′(W_{n}, 1)}{I(W_{n}, 1)}⌋. The independence polynomial I(W_{n}, x) satisfies the recursion

[18, 19, 20]

I(W_{n}, x) = (x + 1) (I(W_{n−1}, x) + xI(W_{n−2}, x)) ,  (2)

with W_{0} = 1, I(W_{1}, x) = 1 + 2x.

Theorem 5. [24] The independence polynomial of the centipede is given by

I(W_{n}, x) = \frac{(x + 1)^{⌊^{\frac{n}{2}}⌋}}{\sqrt{Δ}} ((\frac{3x + 1 + \sqrt{Δ}}{2})^{\frac{n+2}{2}} − (\frac{3x + 1 − \sqrt{Δ}}{2})^{\frac{n+2}{2}} )
= (x + 1)^{⌊^{\frac{n}{2}}⌋}H(x),

where Δ = 5x^{2} + 6x + 1.

Proof. By [24, Lemma 2.3], we have

I(W_{n}, x) = \frac{1}{(x + 1)\sqrt{Δ}} ((\frac{1 + x + \sqrt{Δ}}{2})^{n+2} − (\frac{x + 1 − \sqrt{Δ}}{2})^{n+2}) .

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) =

\frac{1}{(x + 1)\sqrt{Δ}} ((\frac{1 + x + \sqrt{Δ}}{2})^{2l+2} − (\frac{x + 1 − \sqrt{Δ}}{2})^{2l+2})

= \frac{1}{(x + 1)\sqrt{Δ}} (((\frac{1 + x + \sqrt{Δ}}{2})^{2})^{l+1} − ((\frac{x + 1 − \sqrt{Δ}}{2})^{2})^{l+1})

= \frac{1}{(x + 1)\sqrt{Δ}} ((\frac{6x^{2} + 8x + 2 + 2(x + 1)\sqrt{Δ}}{4})^{l+1} − (\frac{6x^{2} + 8x + +2 − 2(x + 1)\sqrt{Δ}}{4})^{l+1})

= \frac{1}{(x + 1)\sqrt{Δ}} ((\frac{3x^{2} + 4x + 1 + (x + 1)\sqrt{Δ}}{2})^{l+1} − (\frac{3x^{2} + 4x + 1 − (x + 1)\sqrt{Δ}}{2})^{l+1})

= \frac{(x + 1)^{l}}{\sqrt{Δ}} ((\frac{3x + 1 + \sqrt{Δ}}{2})^{l+1} − (\frac{3x + 1 − \sqrt{Δ}}{2})^{l+1})
= (x + 1)^{l}H_{l}(x)

For n = 2l + 1, (j = l + 1) we have

I(W_{2l+1}, x) =

\frac{1}{(x + 1)\sqrt{Δ}} ((\frac{1 + x + \sqrt{Δ}}{2})^{2l+3} − (\frac{x + 1 − \sqrt{Δ}}{2})^{2l+3})

= \frac{1}{(x + 1)\sqrt{Δ}} ((\frac{1 + x + \sqrt{Δ}}{2}) ((\frac{1 + x + \sqrt{Δ}}{2})^{2})^{j} − (\frac{x + 1 − \sqrt{Δ}}{2}) ((\frac{x + 1 − \sqrt{Δ}}{2})^{2})^{j})

= \frac{(x + 1)^{j−1}}{\sqrt{Δ}} ((\frac{1 + x + \sqrt{Δ}}{2}) (\frac{3x + 1 + \sqrt{Δ}}{2})^{j} − (\frac{x + 1 − \sqrt{Δ}}{2}) (\frac{3x + 1 − \sqrt{Δ}}{2})^{j})

= \frac{(x + 1)^{j−1}}{\sqrt{Δ}} ((\frac{3x + 1 + \sqrt{Δ}}{2})^{j+ \frac{1}{2}} − (\frac{3x + 1 − \sqrt{Δ}}{2})^{j+ \frac{1}{2}} )

= \frac{(x + 1)^{l}}{\sqrt{Δ}} ((\frac{3x + 1 + \sqrt{Δ}}{2})^{\frac{2l+3}{2}} − (\frac{3x + 1 − \sqrt{Δ}}{2})^{\frac{2l+3}{2}} )
= (x + 1)^{l}H_{l+1}(x)

Gathering all this together, we obtain the desired formula:

I(W_{n}, x) = \frac{(x + 1)^{⌊^{\frac{n}{2}}⌋}}{\sqrt{Δ}} ((\frac{3x + 1 + \sqrt{Δ}}{2})^{\frac{n+2}{2}} − (\frac{3x + 1 − \sqrt{Δ}}{2})^{\frac{n+2}{2}} ) = (x + 1)^{⌊ \frac{n}{2} ⌋}H(x)

(3)

The polynomial H(x) is of degree ⌊\frac{n+1}{2}⌋. 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[9]. Now we can determine the mode of the centipede.

[figure: .............]

Figure 2: The graph L_{n}

[figure: .............]

Figure 3: The graph M_{n}

Theorem 6. Every mode of the independence polynomial of the centipede satisfies

⌊n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \frac{\sqrt{3}}{12}(n + 2) + \frac{1}{3}⌋ ≤ k_{0} ≤ ⌊n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \frac{\sqrt{3}}{12}(n + 2) + \frac{1}{3}⌋ + 1.

Proof. Our aim is to evaluate \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:

H_{r}(x) = x^{⌊ \frac{n+1}{2} ⌋}H(\frac{1}{x})
= \frac{1}{\sqrt{B}} ((\frac{x + 3 + \sqrt{B}}{2} )^{\frac{n+2}{2}} − (\frac{x + 3 − \sqrt{B}}{2} )^{\frac{n+2}{2}} ) ,

where B = x^{2} + 6x + 5. Now

H_{r}′(x) = \frac{(n + 2)}{2B} ((\frac{x + 3 + \sqrt{B}}{2} )^{\frac{n+2}{2}} + (\frac{x + 3 − \sqrt{B}}{2} )^{\frac{n+2}{2}} ) − \frac{(x + 3)}{B}H_{r}(x).

Note that

\frac{I′(W_{n}, 1)}{I(W_{n}, 1)} = \frac{1}{2} ⌊\frac{n}{2}⌋ + \frac{H′(1)}{H(1)}.

But

\frac{H′(1)}{H(1)} = ⌊\frac{n + 1}{2}⌋ − \frac{H′_{r}(1)}{H_{r}(1)},

now

\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},  (a = 7 − 4\sqrt{3} = 0.07179 ⋯)
≥ \sqrt{3}\frac{(n + 2)}{12} − \frac{1}{3}.

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}} ≤ \sqrt{3}\frac{(n + 2)}{12} + \frac{2}{3},

or

\frac{(n + 2)a^{n+2}}{1 − a^{n+2}} ≤ \frac{4}{\sqrt{3}},

which is true, since the function x(e^{αx} − 1)^{−1}, α > 0, is decreasing for x ≥ 1. So,

\frac{I′(W_{n}, 1)}{I(W_{n}, 1)} = \frac{1}{2} ⌊\frac{n}{2}⌋ + \frac{H′(1)}{H(1)}
= \frac{1}{2} ⌊\frac{n}{2}⌋ + ⌊\frac{n + 1}{2}⌋ − \frac{H′_{r}(1)}{H_{r}(1)}
≤ n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \frac{H′_{r}(1)}{H_{r}(1)} ≤ n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \sqrt{3}\frac{(n + 2)}{12} + \frac{1}{3}.

We obtain

⌊\frac{I′(W_{n}, 1)}{I(W_{n}, 1)}⌋ ≤ ⌊n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \sqrt{3}\frac{(n + 2)}{12} + \frac{1}{3}⌋ .  (4)

Also

\frac{I′(W_{n}, 1)}{I(W_{n}, 1)} = \frac{1}{2} ⌊\frac{n}{2}⌋ + \frac{H′(1)}{H(1)}
= \frac{1}{2} ⌊\frac{n}{2}⌋ + ⌊\frac{n + 1}{2}⌋ − \frac{H′_{r}(1)}{H_{r}(1)}
≥ n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \frac{H′_{r}(1)}{H_{r}(1)} ≥ n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \sqrt{3}\frac{(n + 2)}{12} + \frac{1}{3} − \frac{2}{3}
> n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \sqrt{3}\frac{(n + 2)}{12} + \frac{1}{3} − 1.

It follows then that

⌊\frac{I′(W_{n}, 1)}{I(W_{n}, 1)}⌋ ≥ ⌊n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \sqrt{3}\frac{(n + 2)}{12} + \frac{1}{3}⌋ − 1.  (5)

Equations (4) and (5) give the desired result. Corollary 7. For every l ∈ ℕ, l ≥ 1, there exists an integer n_{0} such that

\frac{I′(W_{n}, 1)}{I(W_{n}, 1)} − k_{n} > l, for n ≥ n_{0}.

In other words, the conjecture of Levit and Mandrescu is false. Proof. Let l > 0, be a fixed integer. Then

\frac{I′(W_{n}, 1)}{I(W_{n}, 1)} ≥ n − \frac{1}{2} ⌊\frac{n}{2}⌋ − \sqrt{3}\frac{(n + 2)}{12} + \frac{1}{3} − \frac{2}{3} ≥ \frac{(9 − \sqrt{3})}{12}n − 1.

Also

k_{n} ≤ \frac{3}{5}n + 3.

But for n ≥ 801, say, we have

\frac{I′(W_{n}, 1)}{I(W_{n}, 1)} − k_{n} ≥ \frac{(9 − \sqrt{3})}{12}n − \frac{3}{5}n − 4 ≥ .0005n − 4 > 0,

and then, for n ≥ 200(l + 4) we obtain the desired result.

The calculations agove are not very accurate, and n ≥ 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 ⋯ − 241 = 2.5209 ⋯

For n = 1000,

\frac{I′(W_{1000}, 1)}{I(W_{1000}, 1)} − k_{1000} = 605.707 ⋯ − 600 = 5.707 ⋯

The constant term in H_{r}(x) is F_{n}, the Fibonacci number. Using the results of [24], 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 \underline{A129722}. Also, we may deduce

\begin{aligned}⌊ & \frac{n+1}{2} & ⌋ \\ & ∏ \\ & k=1 \end{aligned} (1 + 4 cos^{2} (\frac{kπ}{n + 2})) = F_{n+1}.

3 The sequence s_{k} is asymptotically normal

A positive real sequence a(n, k)_{k=0}^{n}, with A_{n} = ∑_{k=0}^{n} a(n, k) ≠ 0, is said to satisfy a central

limit theorem (or is asymptotically normal) with mean μ_{n} and variance σ_{n}^{2} if

lim_{n⟶+∞} sup_{x∈R} | ∑_{0≤k≤μ_{n}+xσ_{n}} \frac{a(n, k)}{A_{n}} − (2π)^{−1/2} ∫_{−∞}^{x} e^{− \frac{t^{2}}{2}} dt| = 0.  (6)

The sequence satisfies a local limit theorem on B ⊆ ℝ ; with mean μ_{n} and variance σ_{n}^{2} if

lim_{n⟶+∞} sup_{x∈B} |\frac{σ_{n}a(n, μ_{n} + xσ_{n})}{A_{n}} − (2π)^{−1/2}e^{− \frac{x^{2}}{2}} | = 0.  (7)

Recall the following result (see Bender [2]).

Theorem 8. Let (Q_{n})_{n≥1} be a sequence of real polynomials; with only real negative zeros. The sequence of the coefficients of the (Q_{n})_{n≥1} satisfies a central limit theorem; with μ_{n} = \frac{Q′_{n}(1)}{Q_{n}(1)}

and σ_{n}^{2} = (\frac{Qn^{′′}(1)}{Q_{n}(1)} + \frac{Qn^{′}(1)}{Q_{n}(1)} − (\frac{Qn^{′}(1)}{Q_{n}(1)})^{2}) provided that lim_{n⟶+∞} σ_{n}^{2} = +∞. 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 ℝ.

Generally speaking, a central limit theorem for a sequence of random variables gives (6). Relation (7) is then deduced under the condition that the sequence has no internal zeros (see [2]). Relation (6) is nothing than pointwise convergence. We have the following result

Theorem 9. The sequence s_{k} satisfies a central limit and a local limit theorem on ℝ, with mean

μ_{n} = \frac{I′(W_{n}, 1)}{I(W_{n}, 1)} ≈ \frac{(9 − \sqrt{3})n}{12}

and variance

σ_{n}^{2} = (\frac{I′′(W_{n}, 1)}{I(W_{n}, 1)} + \frac{I′(W_{n}, 1)}{I(W_{n}, 1)} − (\frac{I′(W_{n}, 1)}{I(W_{n}, 1)})^{2}) ≈ \frac{(15 − 2\sqrt{3})n}{24}.

Proof. In order to prove that the sequence of the coefficients of P_{n}(x) is asymptotically normal, let us evaluate

(\frac{I′′(W_{n}, 1)}{I(W_{n}, 1)} + \frac{I′(W_{n}, 1)}{I(W_{n}, 1)} − (\frac{I′(W_{n}, 1)}{I(W_{n}, 1)})^{2}) .

We have

I(W_{n}, x) = (x + 1)^{⌊ \frac{n}{2} ⌋}H(x)
I′(W_{n}, x) = ⌊\frac{n}{2}⌋ (x + 1)^{⌊ \frac{n}{2} ⌋−1}H(x) + (x + 1)^{⌊ \frac{n}{2} ⌋}H′(x)
I′′(W_{n}, x) = ⌊\frac{n}{2}⌋ (⌊\frac{n}{2}⌋ − 1) (x + 1)^{⌊ \frac{n}{2} ⌋−2}H(x) + 2 ⌊\frac{n}{2}⌋ (x + 1)^{⌊ \frac{n}{2} ⌋−1}H′(x) + (x + 1)^{⌊ \frac{n}{2} ⌋}H′′(x).

We also have

\frac{I′(W_{n}, 1)}{I(W_{n}, 1)} = \frac{⌊\frac{n}{2}⌋ (⌊\frac{n}{2}⌋ − 1)}{4} + ⌊\frac{n}{2}⌋ \frac{H′(1)}{H(1)} + \frac{H′′(1)}{H(1)},

so

σ_{n}^{2} = \frac{⌊\frac{n}{2}⌋}{4} + \frac{H”(1)}{H(1)} + \frac{H′(1)}{H(1)} − (\frac{H′(1)}{H(1)})^{2}
= \frac{⌊\frac{n}{2}⌋}{4} + (σ_{n}^{H})^{2}
= \frac{⌊\frac{n}{2}⌋}{4} + \frac{H′(1)}{H(1)} (1 + \frac{H′′(1)}{H′(1)} − \frac{H′(1)}{H(1)}) > \frac{⌊\frac{n}{2}⌋}{4}.

It follows that lim_{n⟶∞} σ_{n} = ∞, and then the sequences s_{k} satisfies a central limit theorem.

Now let (−α_{i}), (−β_{i}), be respectively the zeros of H(x) and H′(x). Then by Rolle’s theorem we get

−α_{1} ≤ β_{1} ≤ −α_{2} ≤ β_{2} ≤ ⋯ ≤ −β_{⌊_{\frac{n+1}{2}}⌋−1} ≤ −α⌊_{\frac{n+1}{2}}⌋.

We deduce

(1 + \frac{H′′(1)}{H′(1)} − \frac{H′(1)}{H(1)}) = \begin{matrix}⌊ & \frac{n+1}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} \frac{α_{i}}{1 + α_{i}} − ∑_{i=1}^{⌊\frac{n+1}{2}⌋−1} \frac{β_{i}}{1 + β_{i}} ,
= \frac{H′_{r}(1)}{H_{r}(1)} − \frac{H′′_{r}(1)}{H′_{r}(1)} ≈ 1

It follows that

σ_{n}^{2} ≈ \frac{(15 − 2\sqrt{3})n}{24}

By Theorem 8, and because all the s_{k} are nonvanishing, we have a local limit theorem, from which we deduce the

Corollary 10. Let S_{k_{0}} = max_{k} s_{k}. Then we have the approximation of the maximum stable set

S_{k_{0}} ≈ \frac{I(W_{n}, 1)}{σ_{n}} ≈ 1.02\frac{(1 + \sqrt{3})^{n}}{\sqrt{πn}}

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}.

4 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.

References

[1] Y. Alavi, P. J. Malde, A. J. Schwenk, and P. Erdős, The vertex independence sequence of a graph is not constrained, Congr. Numer. 58 (1987), 15–23.

[2] E. A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Combin. Theory Ser. A 15 (1973), 91–111.

[3] M. Benoumhani, Polynômes à racines réelles négatives et applications combinatoires. Ph. D. Thesis, Claude Bernard University, Lyon, France, 1993.

[4] M. Benoumhani, Sur une propriété des polynômes à racines réelles négatives, J. Math. Pures Appl. (1996), 85–110.

[5] C. Berge, Some common properties for regularizable graphs, edge-critical graphs and B-graphs, Ann. Discrete Math. 12 (1982), 31–44.

[6] J. A. Bondy and S. R. Murty, Graph Theory and Applications, Elsevier, 1982.

[7] F. Brenti, Log-concave, unimodal sequences in algebra, combinatorics, and geometry, Contemp. Math 178 (1994), 71–89.

[8] V. Chvatal and P. J. Slater, A note on well-covered graphs, Ann. Discrete Math., 55 (1993), 179–182.

[9] M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B 97 (2007), 350–357.

[10] J. N. Darroch, On the distribution of the number of successes in independent trials, Ann. Math. Stat. 35 (1964), 1317–1321.

[11] R. Durrett, Probability: Theory and Examples, Duxbury Press, 1994.

[12] A. Finbow, B. Hartnell, and R. J. Nowakowski, Well dominated graphs: a collection of well-covered ones, Ars Combin. 25 (1988), 5–10.

[13] I. Gutman and F. Harary, Generalizations of the matching polynomial, Util. Math. 24 (1983), 97-106.

[14] A. Finbow, B. Hartnell, and R. J. Nowakowski, A characterization of well covered graphs which contain neither 4- nor 5-cycles, J. Graph Theory 18 (1994), 713–721.

[15] Y. O. Hamidoune, On the number of the independent k-sets in a claw free graph, J. Combin. Theory Ser. B 50 (1990), 241–244.

[16] E. L. C. King, Characterising a subclass of well-covered graphs, Congr. Numer. 160 (2003), 7–31.

[17] V. E. Levit and E. Mandrescu, Well-covered trees, Congr. Numer. 139 (1999), 101–112.

[18] V. E. Levit and E. Mandrescu, On well-covered trees with unimodal independence polynomials, Congr. Numer. 159 (2002) 193–202.

[19] 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., 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.

[20] V. E. Levit and E. Mandrescu, Independence polynomial of a graph–a survey. In S. Bozapalidis, A. Kalampakas, and G. Rahonis, eds., Proceedings of the 1st International Conference on Algebraic Informatics, 2005, pp. 233-254.

[21] D. M. Plummer, Some covering concepts in graphs, J. Combin. Theory Ser. B, 8 (1970), 91–98.

[22] D. M. Plummer, Well-covered graphs: a survey, Quaestiones Math. 16 (1993), 253–287.

[23] N. J. A. Sloane, The Encyclopedia of Integer Sequences. Published electronically at http://oeis.org, 2011.

[24] Y. Wang and B.-X. Zhu, On unimodality of independence polynomials of some graphs, European J. Combin. 32 (2011), 10–20.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B75. Keywords: Independence polynomial, centipede, log-concave sequence, limit theorem, polynomial with real zeros, unimodal sequence, Fibonacci number.

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

Received October 21 2011; revised version received April 14 2012. Published in Journal of Integer Sequences, April 20 2012.

Return to Journal of Integer Sequences home page.