超环面图上的约束数(英文)  

On bondage number of toroidal graphs

作　　者：曹永昌[1] 徐俊明[1] 徐喜荣[2] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026 [2]大连理工大学计算机系,辽宁大连116024

出　　处：《中国科学技术大学学报》2009年第3期225-228,共4页JUSTC

基　　金：Supported by NNSF of China(10671191).

摘　　要：非空图G的约束数b(G)是指使得图G的控制数γ(G)增大而删除的最少的边数.[Fischermann M,Rautenbach D,Volkmann L.Remarks on the bondage number of planar graphs.Discrete Math,2003,260:57-67]已经证明,对于一个围长为g(G)的平面图G,如果g(G)≥4则b(G)≤6,如果g(G)≥5则b(G)≤5,如果g(G)≥6则b(G)≤4,如果g(G)≥8则b(G)≤3.我们把这个结果推广到连通的超环面图中.The bondage number b（G） of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with the domination number greater than the domination number γ（G） of G. [-Fisehermann M, Rautenbach D, Volkmann L. Remarks on the bondage number of planar graphs. Discrete Math,2003,260：57-67] showed that for a connected planar graph G with girth g（G）, b（G）≤6 if g（G）≥4, b（G）≤5 if g（G）≥5, b（G）≤4 if g（G）≥6 and b（G）≤3 if g（G）≥8. This result was generalized to a connected toroidal graph that was embeddable on the torus.

关 键 词：约束数 控制数 交叉数 平面图 

分 类 号：O157.5[理学—数学]