最大度至多为3的图上极大分离集的最大数目

给定图G=（V，E），若顶点子集F在图G中的导出子图的最大度至多为1，则称F为图G的一个分离集；若F不是其他分离集的真子集，则称F为一个极大分离集。对极大分离集计数问题进行研究，证明了在所有n个顶点且最大度至多为3的图上最多有\begin{document}${6^{\frac{\mathit{n}}{{\rm{4}}}}}$\end{document}个极大分离集，并刻画了相应的极图结构。

On the maximum number of maximal dissociation sets in graphs with maximum degree at most three

A subset of vertices F in a graph G is a dissociation set if the induced subgraph GF] has maximum degree at most one. If F is not a proper subset of any other dissociation sets, then F is a maximal dissociation set of G. Obviously, the dissociation set is a natural generalization of the independent set. In this paper, the counting problem of maximal dissociation sets is considered. We show that there are at most \begin{document}$ {6^{\frac{\mathit{n}}{{\rm{4}}}}}$\end{document} maximal dissociation sets in n-vertex graphs with maximum degree at most three. The extremal graphs achieving the maximum value have also been completely characterized.