Upper bounds on the bondage number of a graph

被引：0

作者：

Samodivkin, Vladimir ^{[1
]}

机构：

[1] Univ Architecture Civil Engn & Geodesy, Dept Math, Sofia, Bulgaria

来源：

ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS | 2018年 / 6卷 / 01期

关键词：

bondage number; domination number; Euler's formula; girth; average degree;

D O I：

10.5614/ejgta.2018.6.1.1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The bondage number b(G) of a graph G is the smallest number of edges whose removal from G results in a graph with larger domination number. We obtain sufficient conditions for the validity of the inequality b(G) <= 2s - 2, provided G has degree s vertices. We also present upper bounds for the bondage number of graphs in terms of the girth, domination number and Euler characteristic. As a corollary we give a stronger bound than the known constant upper bounds for the bondage number of graphs having domination number at least four. Several unanswered questions are posed.

引用

页码：1 / 16

页数：16

共 31 条

[1]

Altshuler A., 1973, Discrete Mathematics, V4, P201, DOI 10.1016/S0012-365X(73)80002-0

[2] DOMINATION ALTERATION SETS IN GRAPHS [J].

BAUER, D ;

HARARY, F ;

NIEMINEN, J ;

SUFFEL, CL .

DISCRETE MATHEMATICS, 1983, 47 (2-3) :153-161

[3] On the bondage number of planar and directed graphs [J].

Carlson, Kelli ;

Develin, Mike .

DISCRETE MATHEMATICS, 2006, 306 (8-9) :820-826

[4] THE BONDAGE NUMBER OF A GRAPH [J].

FINK, JF ;

JACOBSON, MS ;

KINCH, LF ;

ROBERTS, J .

DISCRETE MATHEMATICS, 1990, 86 (1-3) :47-57

[5]

Frucht R., 1970, AEQUATIONES MATH, V4, P322, DOI DOI 10.1007/BF01844162

[6] Upper bounds for the bondage number of graphs on topological surfaces [J].

Gagarin, Andrei ;

Zverovich, Vadim .

DISCRETE MATHEMATICS, 2013, 313 (11) :1132-1137

[7] The bondage number of graphs on topological surfaces and Teschner's conjecture [J].

Gagarin, Andrei ;

Zverovich, Vadim .

DISCRETE MATHEMATICS, 2013, 313 (06) :796-808

[8]

Hartnell BL, 1999, DISCRETE MATH, V197, P409

[9] BOUNDS ON THE BONDAGE NUMBER OF A GRAPH [J].

HARTNELL, BL ;

RALL, DF .

DISCRETE MATHEMATICS, 1994, 128 (1-3) :173-177

[10] A BOUND ON THE BONDAGE NUMBER OF TOROIDAL GRAPHS* [J].

Hou, Jianfeng ;

Liu, Guizhen .

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (03)

← 1 2 3 4 →