图的圈和树孤立

作者：张刚; 吴宝音都仍^*

来源：新疆大学学报(自然科学版)(中英文), 2022, 39(02): 169-175.

DOI：10.13568/j.cnki.651094.651316.2021.03.06.0004

• 孤立数
• 圈
• 树
• 部分控制

对任一图G,如果顶点子集D使得G-N[D]不包含任何一个F中的F图作为子图,那么D被叫做图G的一个F孤立集,其中F是一个连通图集.图G中最小的一个F孤立集D的阶数被称为图G的F孤立数,记为ι(G,F).特别的,当F={C3, K1,3, P4}时,定义ι(G,{C3, K1,3, P4})=ι′c(G).于是,图G中任一{C3, K1,3, P4}孤立集D使得G-N [D]只是一些K1, K2和P3分支,而ιc′(G)表示图G中最小的一个{C3, K1,3, P4}孤立集D的阶数.本文证明了如果G?{C3, C7}是一个顶点数为n的连通图,那么ι′c(G)≤n/4,且这个上界是最好的.

• 出版日期2022