# The bondage number of graphs: good and bad vertices

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 3, page 453-462
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topVladimir Samodivkin. "The bondage number of graphs: good and bad vertices." Discussiones Mathematicae Graph Theory 28.3 (2008): 453-462. <http://eudml.org/doc/270385>.

@article{VladimirSamodivkin2008,

abstract = {The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater then γ(G). In this paper we present new sharp upper bounds for b(G) in terms of γ-good and γ-bad vertices of G.},

author = {Vladimir Samodivkin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {bondage number; γ-bad/good vertex; -bad/good vortex},

language = {eng},

number = {3},

pages = {453-462},

title = {The bondage number of graphs: good and bad vertices},

url = {http://eudml.org/doc/270385},

volume = {28},

year = {2008},

}

TY - JOUR

AU - Vladimir Samodivkin

TI - The bondage number of graphs: good and bad vertices

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 3

SP - 453

EP - 462

AB - The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater then γ(G). In this paper we present new sharp upper bounds for b(G) in terms of γ-good and γ-bad vertices of G.

LA - eng

KW - bondage number; γ-bad/good vertex; -bad/good vortex

UR - http://eudml.org/doc/270385

ER -

## References

top- [1] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient Dominating Sets in Graphs, in: R.D. Ringeisen and F.S. Roberts (Eds.), Applications of Discrete Mathematics (SIAM, Philadelphia, PA, 1988) 189-199. Zbl0664.05027
- [2] D. Bauer, F. Harary, J. Nieminen and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983) 153-161, doi: 10.1016/0012-365X(83)90085-7. Zbl0524.05040
- [3] R.C. Brigham, P.Z. Chinn and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988) 173-179, doi: 10.1002/net.3230180304. Zbl0658.05042
- [4] J.R. Carrington, F. Harary and T.W. Haynes, Changing and unchanging the domination number of a graph, J. Combin. Math. Combin. Comput. 9 (1991) 57-63. Zbl0736.05067
- [5] J.E. Dunbar, T.W. Haynes, U. Teschner and L. Volkmann, Bondage, insensitivity and reinforcement, in: T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998) 471-489. Zbl0894.05025
- [6] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47-57, doi: 10.1016/0012-365X(90)90348-L. Zbl0745.05056
- [7] G.H. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and R.C. Laskar, Excellent trees, Bull. Inst. Comb. Appl. 34 (2002) 27-38.
- [8] J. Fulman, D. Hanson and G. MacGillivray, Vertex domination-critical graphs, Networks 25 (1995) 41-43, doi: 10.1002/net.3230250203. Zbl0820.05038
- [9] B.L. Hartnell and D.F. Rall, Bounds on the bondage number of a graph, Discrete Math. 128 (1994) 173-177, doi: 10.1016/0012-365X(94)90111-2. Zbl0796.05051
- [10] B.L. Hartnell and D.F. Rall, A bound on the size of a graph with given order and bondage number, Discrete Math. 197/198 (1999) 409-413, doi: 10.1016/S0012-365X(99)90093-6. Zbl0960.05074
- [11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in graphs (Marcel Dekker, Inc., New York, NY, 1998). Zbl0890.05002
- [12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in graphs: Advanced topics (Marcel Dekker, Inc., New York, NY, 1998). Zbl0883.00011
- [13] Hailong Liu and Liang Sun, The bondage and connectivity of a graph, Discrete Math. 263 (2003) 289-293, doi: 10.1016/S0012-365X(02)00770-7. Zbl1014.05050
- [14] U. Teschner, A counterexample to a conjecture on the bondage number of a graph, Discrete Math. 122 (1993) 393-395, doi: 10.1016/0012-365X(93)90317-M. Zbl0787.05060
- [15] U. Teschner, A new upper bound for the bondage number of a graphs with small domination number, Aus. J. Combin. 12 (1995) 27-35. Zbl0839.05053
- [16] U. Teschner, The bondage number of a graphs G can be much greater than Δ(G), Ars. Combinatoria 43 (1996) 81-87. Zbl0881.05062
- [17] U. Teschner, New results about the bondage number of a graph, Discrete Math. 171 (1997) 249-259, doi: 10.1016/S0012-365X(96)00007-6. Zbl0881.05067
- [18] Yue-Li Wang, On the bondage number of a graph, Discrete Math. 159 (1996) 291-294, doi: 10.1016/0012-365X(96)00347-0. Zbl0860.05045

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.