On trees with real-rooted independence polynomial

The independence polynomial of a graph $G$ is

$I(G,x)=\sum _{k\ge 0}{i}_k\left(G\right)x^k,$

where $i_k\left(G\right)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0\left(G\right)=1$). In this paper we show a new method to prove real-rootedness of the independence polynomials of certain families of trees.In particular we will give a new proof of the real-rootedness of the independence polynomials of centipedes (Zhu’s theorem), caterpillars (Wang and Zhu’s theorem), and we will prove a conjecture of Galvin and Hilyard about the real-rootedness of the independence polynomial of the so-called Fibonacci trees.     

On the roots of Wiener polynomials of graphs

The Wiener polynomial of a connected graph $G$ is defined as $W(G;x)=\sum x^{d(u,v)}$, where $d(u,v)$ denotes the distance between $u$ and $v$, and the sum is taken over all unordered pairs of distinct vertices of $G$. We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order $n$ is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)?1$, the maximum modulus among all roots of Wiener polynomials of trees of order $n$ grows linearly in $n$. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely $(?\infty ,0]$, while in the case of trees, it contains $(?\infty ,?1]$. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.     

A note on permutation polynomials over finite fields

Permutation polynomials over finite fields constitute an active research area and have applications in many areas of science and engineering. In this paper, two conjectures on permutation polynomials proposed recently by Wu and Li [19] are settled. Moreover, a new class of permutation trinomials of the form $x+\gamma {\mathrm{Tr}}_{q^n/q}(x^k)$ is also presented, which generalizes two examples of [10].     

Necessary conditions for reversed Dickson polynomials of the second kind to be permutational

In this paper, we present several necessary conditions for the reversed Dickson polynomial $E_n(1,x)$ of the second kind to be a permutation of ${\mathbb{F}}_q$. In particular, we give explicit evaluation of the sum ${\sum }_{a\in {\mathbb{F}}_q}{E}_n(1,a)$.