Maximum dissociation sets in subcubic trees

Lei Zhang, Jianhua Tu, Chunlin Xin

Published 2020-05-07Version 1

A subset of vertices in a graph $G$ 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 of $G$, denoted by $\psi(G)$, is the cardinality of a maximum dissociation set. A subcubic tree is a tree of maximum degree at most 3. In this paper, we give the lower and upper bounds on the dissociation number in a subcubic tree of order $n$ and show that the number of maximum dissociation sets of a subcubic tree of order $n$ and dissociation number $\psi$ is at most $1.466^{4n-5\psi+2}$.