Random procedures for dominating sets in bipartite graphs

Sarah Artmann; Jochen Harant

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 2, page 277-288
  • ISSN: 2083-5892

Abstract

top
Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.

How to cite

top

Sarah Artmann, and Jochen Harant. "Random procedures for dominating sets in bipartite graphs." Discussiones Mathematicae Graph Theory 30.2 (2010): 277-288. <http://eudml.org/doc/270924>.

@article{SarahArtmann2010,
abstract = {Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.},
author = {Sarah Artmann, Jochen Harant},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; bipartite graph; multilinear function; random procedure},
language = {eng},
number = {2},
pages = {277-288},
title = {Random procedures for dominating sets in bipartite graphs},
url = {http://eudml.org/doc/270924},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Sarah Artmann
AU - Jochen Harant
TI - Random procedures for dominating sets in bipartite graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 2
SP - 277
EP - 288
AB - Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.
LA - eng
KW - domination; bipartite graph; multilinear function; random procedure
UR - http://eudml.org/doc/270924
ER -

References

top
  1. [1] N. Alon and J. Spencer, The Probabilistic Method (John Wiley and Sons, Inc., 1992). Zbl0767.05001
  2. [2] V.I. Arnautov, Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices, (Russian), Prikl. Mat. Programm. 11 (1974) 3-8. 
  3. [3] S. Artmann, F. Göring, J. Harant, D. Rautenbach and I. Schiermeyer, Random procedures for dominating sets in graphs, submitted. Zbl1230.05222
  4. [4] Y. Caro, New results on the independence number (Technical Report. Tel-Aviv University, 1979). 
  5. [5] Y. Caro and Y. Roditty, On the vertex-independence number and star decomposition of graphs, Ars Combin. 20 (1985) 167-180. Zbl0623.05031
  6. [6] Y. Caro and Y. Roditty, A note on the k-domination number of a graph, Internat. J. Math. Sci. 13 (1990) 205-206, doi: 10.1155/S016117129000031X. Zbl0706.05033
  7. [7] G.J. Chang and G.L. Nemhauser, The k-domination and k-stability problems in sun-free chordal graphs, SIAM J. Algebraic Discrete Methods 5 (1984) 332-345, doi: 10.1137/0605034. Zbl0576.05054
  8. [8] F. Göring and J. Harant, On domination in graphs, Discuss. Math. Graph Theory 25 (2005) 7-12, doi: 10.7151/dmgt.1254. Zbl1077.05075
  9. [9] J. Harant and A. Pruchnewski, A note on the domination number of a bipartite graph, Ann. Combin. 5 (2001) 175-178, doi: 10.1007/PL00001298. Zbl0987.05078
  10. [10] J. Harant, A. Pruchnewski, and M. Voigt, On dominating sets and independendent sets of graphs, Combin. Prob. Comput. 8 (1999) 547-553, doi: 10.1017/S0963548399004034. Zbl0959.05080
  11. [11] J. Harant and D. Rautenbach, Domination in bipartite graphs, Discrete Math. 309 (2009) 113-122, doi: 10.1016/j.disc.2007.12.051. Zbl1181.05069
  12. [12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
  13. [13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs Advanced Topics (Marcel Dekker, Inc., New York, 1998). Zbl0883.00011
  14. [14] C. Payan, Sur le nombre d'absorption d'un graphe simple, (French), Cah. Cent. Étud. Rech. Opér. 17 (1975) 307-317. Zbl0341.05126
  15. [15] V.K. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum 81-11217-9 (Murray Hill, NJ, 1981). 

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.