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

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