禁用两个子图的图的全控制数

设G=V(V,E)是一个简单无向图.一个点悬挂三个一度点的图称为爪图,D图是一个三角形其中两个点各悬挂一条长为2的路.如果图G的任何导出子图都不同构于爪图也不同构于D图,则称G为无爪和无D图.设S是V的非空子集,如果不在S的点一定与S中的某个点相邻,则称S为G的控制集.如果G中的点一定与S中的某个点相邻,则S称为G的全控制集.最小全控制集包含顶点的数目称为全控制数.给出了当G是N阶连通的无爪和无D图时全控制数紧的上界.

禁用两个子图的图的成对控制数

禁用子图条件下图参数的界是图论研究的重要内容。主要应用组合结构分析方法研究禁用两个子图的成对控制数。设D是V的非空子集,如果不在D的点一定与D中的某个点相邻,则称D为G的控制集。如果不含孤立点图G的控制集的导出子图包含完美匹配,则D称为G的成对控制集。最小成对控制集包含顶点的数目称为成对控制数。文章主要给出了当G是n阶连通的无爪和无埃菲尔图时成对控制数紧的上界。本文结果丰富了图的成对控制数的研究。