立方图的对控制数

设G=(V,E)是一个简单图,对任意的顶点子集合S■V,G[S]表示图G中由S所导出的子图．如果S是G的一个控制集并且G[S]包含至少一个完备匹配,则称S是G的一个对控制集．G中对控制集的最少的顶点数称为G的对控制数,记为γp(G)．该文证明了对任意有n点的连通立方图G,γp(G)≤(3n)/5．

几类图的负对控制数

设D V是图G=(V,E)的任意一个对控制集,如果一个函数f:V→{-1,0,1}满足条件1)对任意点v∈D,有f(v)=1,对任意点v∈V-D,有f(v)≤0,2)对任意点v∈V,均有f(N[v])≥1,则称函数f为图G的负对控制函数。负对控制函数f的重量f(V)是V中所有点的函数值之和,图G的负对控制数γp-(G)=min{f(V)|f是图G的负对控制函数}。本文研究一些图的负对控制数。

关于图的负对控制数的界

设D V是图G=(V,E)的任意一个对控制集。如果一个函数f:V→{-1,0,1}满足条件:(1)对任意点υ∈D,有f(v)=1,对任意点v-D,有f(v)≤0;(2)对任意点v∈V,均有f(N[v])≥1;则称函数f为图G的负对控制函数。负对控制函数f的重量f(V)是v中所有点的函数值之和,图G的负对控制数γ-P(G)=min{f(V)|f是图G的负对控制函数}。本文研究了图的负对控制数的界。

基于对控制数与双控制数强相等的图

给出基于对控制数与双控制数强相等的图的一个性质,并依据该性质,刻画了基于对控制数与双控制数强相等的树及单圈图.