Number of maximum independent sets on trees

DANIEL A. JAUME

Qawra - St. Paul?s Bay

Conferencia; The Second Malta Conference in Graph Theory and Combinatorics; 2017

Department of Mathematics, Faculty of Science, of the University of Malta

In 1986 Wilf proved that the largest number of maximal independent sets in a tree is $1+2^{\frac{n}{2}-1}$ for $n \geq 2$ and even, and $2^{\frac{n-1}{2}}$ for n odd, see [3]. In 1988 Sagan, [2], gave a short graph-theoretic proof of the Wilf result and characterized the extremal trees. Later, Wilf posed the following question: Which is the greatest number of maximum independent sets for a tree T of order n? In 1991 Zito, in her work [3], proved that the greatest number of maximum independent sets for a tree T of order $n$ is \[\left\{ \begin{table}lr2^{\frac{n-3}{2}} & \text{for odd } n >1,\\1+2^{\frac{n-2}{2}} & \text{for even } n.\end{table}\right.\]In this work, by using the null decomposition of trees introduced by Jaume andMolina in [1], we prove that for any tree $T$\[\nu(T)=\alpha(T)-null(T)\]where $\nu(T)$ is the matching number of $T$, $\alpha(T)$ is the independence number of $T$, and $null(T)$ is the dimension of the null space of the adjacency matrix of T. Furthermore we prove that for any tree $T$ \[a(T) = \prod_{N \in \mathcal{F}_{N}(T)} a(N)\]where $a(T)$ is the number of maximum independent sets of $T$, and $\mathcal{F}_{N}(T)$ is the N-forest of T, see [1]. This last formula allows us to build parallelizable algorithms in order to enumerate and nd all the maximum independent sets on any tree. References:[1] D.A. Jaume and G. Molina, Null decomposition of trees, submitted (2016).[2] B.E. Sagan, A note on independent sets in trees, SIAM Journal on DiscreteMathematics 1 (1988) 105-108.[3] H. S. Wilf, The number of maximal independent sets in a tree, SIAM Journalon Algebraic Discrete Methods 7 (1986) 125-130.[4] J. Zito, The structure and maximum number of maximum independent sets intrees, Journal of Graph Theory 15 (1991) 207-221.