摘要
论文主要研究1-平面图上关于点集S的i-弱化(a∶b)-可选问题和图的分数全控制划分问题. S为图G的一个顶点子集,a、b、i为正整数, 其中a≥b≥i. 我们称图G顶点的一个列表指派L = {L(v)∶v∈V(G)}为定义在G的顶点集V(G)上的一个映射,其中L(v)是由多个元素组成的集合.如果对于任意列表指派L={L(v)∶|L(v)|=a, v∈V(G)}, 都存在V(G)→L的子集族的映射fL满足: (1) 对于任意v∈ S ,|fL(v)|=i; (2) 对于任意u∈V(G)\S,|fL(u)|=b; (3) 对于任意xy∈E(G), fL(x)∩fL(y)=?, 则称图G关于点集S是i-弱化(a∶b)-可选的. 给定点集S为由图中所有4度点组成的顶点子集. 我们证明了对于任意正整数b≥i, 每个不含4-圈和5-圈的1-平面图关于给定点集S是i-弱化(4b+i∶b)-可选的,每个不含3-圈和5-圈以及相邻4-圈的1-平面图关于给定点集S也是i-弱化(4b+i∶b)-可选的. 基于上述两个定理, 我们得到了每个不含4-圈和5-圈的1-平面图是5-可选的等若干个关于1-平面图的可选问题的推论. 给定图G的顶点子集S,如果G中每个顶点都至少与S中一个顶点相邻,则称S为G的一个全控制集. 令(F)={F∶F为图G的全控制集}. 对于任意F(≤)(F), |F|代表F中所含全控制集的个数. 令rF为G中顶点在F中出现的最大次数. 图G的分数全控制划分数FTD(G)=supF|F|/rF. 我们证明了最小度至少为2的可迹图以及不含6-圈、8-圈、10-圈的平面图的分数全控制划分数都以3/2为下界,并且这两个结论是紧的. 我们还证明了每个最小度至少为2的图的Mycielskian图具有两个不交的全控制集,进而其分数全控制划分数至少为2.
NETL