Maximum dissociation sets in subcubic trees

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 $ψ(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 $ψ$ is at most $1.466^{4n-5ψ+2}$.

No reviews yet.

No comments yet.