论文部分内容阅读
设G=(V,E)是一个简单图，定义函数f:E→{-1，+l}。如果G的任意一个诱导圈C都满足f(C)=∑f(e)≥l，则称f为图G的诱导圈符号控制函数(signed cycledomination function)，简记为SCDE同时定义γ(G)=min{f(G)lf是G的一个SCDF}为图G的诱导圈符号控制数(signed cycle domination number)。
本文主要研究了极大平面图，2连通平面图和最小度为3的图的诱导圈符号控制数。主要结果如下：
(1)设G(IV(G)I=，n)是一个极大平面图，γsc(G)=n-2当且仅当它的所有诱导圈都是c。
(2)设G(IV(G)I=n)是一个极大平面图，γ(G)≥n当且仅当G有一个诱导圈C，其中k≥4。
(3)若G是一个2-连通平面图，则γ(G)≥1。
(4)任意δ(G)=3的图G，若γ(G)有常数下界，则γ(G)≥2。
上述关于极大平面图的结果，否定了徐宝根在[On signed cycle domination ingraphs,Discrete Math.309(2009)1007-1012]中的一个猜想。