BOUNDS ON THE BONDAGE NUMBER OF A GRAPH

被引：62
作者：
HARTNELL, BL
RALL, DF
机构：
[1] ST MARYS UNIV,DEPT MATH & COMP SCI,HALIFAX B3H 3C3,NS,CANADA
[2] FURMAN UNIV,DEPT MATH,GREENVILLE,SC 29613
来源：
DISCRETE MATHEMATICS | 1994年 / 128卷 / 1-3期
关键词：
D O I：
10.1016/0012-365X(94)90111-2
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The bondage number b(G) of a graph G is the minimum cardinality of a set of edges of G whose removal from G results in a graph with domination number larger than that of G. Several new sharp upper bounds for b(G) are established. In addition, we present an infinite class of graphs each of whose bondage number is greater than its maximum degree plus one, thus showing a previously conjectured upper bound to be incorrect.
引用
收藏
页码：173 / 177
页数：5
相关论文
共 4 条
[1]   DOMINATION ALTERATION SETS IN GRAPHS [J].
BAUER, D ;
HARARY, F ;
NIEMINEN, J ;
SUFFEL, CL .
DISCRETE MATHEMATICS, 1983, 47 (2-3) :153-161
[2]   THE DISCIPLINE NUMBER OF A GRAPH [J].
CHVATAL, V ;
COOK, W .
DISCRETE MATHEMATICS, 1990, 86 (1-3) :191-198
[3]   THE BONDAGE NUMBER OF A GRAPH [J].
FINK, JF ;
JACOBSON, MS ;
KINCH, LF ;
ROBERTS, J .
DISCRETE MATHEMATICS, 1990, 86 (1-3) :47-57
[4]  
HARTNELL BL, 1992, ARS COMBINATORIA, V33, P65
1