| 超环面图上的约束数 |
| |
| 引用本文： | 曹永昌,徐俊明,徐喜荣.超环面图上的约束数[J].中国科学技术大学学报,2009,39(3). |
| |
| 作者姓名： | 曹永昌 徐俊明 徐喜荣 |
| |
| 作者单位： | 1. 中国科学技术大学数学系,安徽合肥,230026
2. 大连理工大学计算机系,辽宁大连,116024 |
| |
| 摘 要： | 非空图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.我们把这个结果推广到连通的超环面图中.
|
| 关 键 词： | 约束数 控制数 交叉数 平面图 |
On bondage number of toroidal graphs |
| |
| CAO Yong-chang,XU Jun-ming,XU Xi-rong.On bondage number of toroidal graphs[J].Journal of University of Science and Technology of China,2009,39(3). |
| |
| Authors: | CAO Yong-chang XU Jun-ming XU Xi-rong |
| |
| Abstract: | 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. Fischermann 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. |
| |
| Keywords: | bondage number domination number crossing number planar graph |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
