THE BONDAGE NUMBER OF A GRAPH

被引：122

作者：

FINK, JF

JACOBSON, MS

KINCH, LF

ROBERTS, J

机构：

[1] Department of Mathematics, University of Louisville, Louisville

来源：

DISCRETE MATHEMATICS | 1990年 / 86卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(90)90348-L

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A set D of vertices in a graph G is a dominating set if each vertex of G that is not in D is adjacent to at least one vertex of D. The minimum cardinality among all dominating sets in G is called the domination number of G and denoted sigma(G). We define the bondage number b(G) of a graph G to be the cardinality of a smallest set E of edges for which sigma(G-E) > sigma(G). Sharp bounds are obtained for b(G), and the exact values are determined for several classes of graphs.

引用

页码：47 / 57

页数：11