On the maximum number of maximum dissociation sets in trees with given dissociation number

Jianhua Tu, Lei Zhang, Junfeng Du

Published 2021-03-02Version 1

Given a graph $G$, a subset of vertices is called a maximum independent set if no two of the vertices are adjacent and the subset has maximum cardinality. The independence number $\alpha(G)$ of $G$ is the cardinality of a maximum independent set. A subset of vertices is called a maximum dissociation set if it induces a subgraph with vertex degree at most 1 and the subset has maximum cardinality. The dissociation number $\psi(G)$ of $G$ is the cardinality of a maximum dissociation set. Alvarado et al. [Discrete Math. 342 (2019) 934--942] proved that a tree $T$ of independence number $\alpha$ has at most $2^{\alpha-1}+1$ maximum independent sets. In this paper, we consider the corresponding problem for dissociation sets and show that the number of maximum dissociation sets in a tree of dissociation number $\psi$ is at most \begin{center} $\left\{ \begin{array}{ll} 1,& \hbox{if $\psi=1$;} 3^{\tfrac{\psi-1}{2}-1}+1,& \hbox{if $\psi$ is odd and $\psi>1$.} 3^{\tfrac{\psi}{2}-1}+\tfrac{\psi}{2}+1,& \hbox{if $\psi$ is even.} \end{array} \right.$ \end{center} We also characterize those trees achieving this maximum value.