摘要
图G的绑定数b(G)是指边集合的最少边数,当这个边集合从G中去掉后所 得图的控制数大于G的控制数． Fischermann等人在[3]中给出了两个猜想: (1)如果 G是一个连通的平面图且围长g(G)≥4,则b(G)≤5;(2)如果G是一个连通的平面图且 围长g(G)≥5,则b(G)≤4．设n3表示度为3的顶点个数,r4和r5分别表示长为4和 5的圈的个数．本文,我们证明了如果r4<(5n3)/2+10,则猜想1成立;如果r5<12,则猜 想2成立．
The bondage number b（G） of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. Fischermann et al. [3] gave two conjectures： （1） If G is a connected planar graph wih girth g（G） ≥ 4, then b（G） ≤ 5; （2） If G is aconnected planar graph wih girth g（G） ≥ 5, then b（G） ≤ 4. Let n3 be the number of vertices of degree3. Let r4 and rsdenote the number of cycles with length 4 and 5 respectively. In this paper, we prove that Conjecture 1 is valid for r4 〈5n3/2 ＋ 10 and Conjecture 2 is valid for r5 〈 12.
出处
《应用数学与计算数学学报》
2005年第2期85-88,共4页
Communication on Applied Mathematics and Computation
基金
汕头大学自然科学基金资助
关键词
绑定数
平面图
围长
bondage number, planar graph, girth
