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

摘要：

给定图G=(V,E),若顶点子集F在图G中的导出子图的最大度至多为1,则称F为图G的一个分离集;若F不是其他分离集的真子集,则称F为一个极大分离集.对极大分离集计数问题进行研究,证明了在所有n个顶点且最大度至多为3的图上最多有6n/4个极大分离集,并刻画了相应的极图结构.

关键词：最大度为3的图、分离集、极大分离集

所属期刊栏目：49

分类号：O157.5(代数、数论、组合理论)

资助基金：北京市自然科学基金面上项目1222012

在线出版日期：2022-09-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：102-107