The bondage number of graphs: good and bad vertices

Vladimir Samodivkin

Discussiones Mathematicae Graph Theory (2008)

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

Abstract

top
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.

How to cite

top

Vladimir 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in graphs (Marcel Dekker, Inc., New York, NY, 1998). Zbl0890.05002
  12. [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. [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. [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. [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. [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. [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. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.