Geodesic
Random procedures for dominating sets in bipartite graphs
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 277-288.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: domination, bipartite graph, multilinear function, random procedure 
@article{DMGT_2010_30_2_a9,
     author = {Artmann, Sarah and Harant, Jochen},
     title = {Random procedures for dominating sets in bipartite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {277--288},
     publisher = {mathdoc},
     volume = {30},
     number = {2},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a9/}
}
TY  - JOUR
AU  - Artmann, Sarah
AU  - Harant, Jochen
TI  - Random procedures for dominating sets in bipartite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 277
EP  - 288
VL  - 30
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a9/
LA  - en
ID  - DMGT_2010_30_2_a9
ER  - 
%0 Journal Article
%A Artmann, Sarah
%A Harant, Jochen
%T Random procedures for dominating sets in bipartite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 277-288
%V 30
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a9/
%G en
%F DMGT_2010_30_2_a9
Artmann, Sarah; Harant, Jochen. Random procedures for dominating sets in bipartite graphs. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 277-288. http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a9/

[1] N. Alon and J. Spencer, The Probabilistic Method (John Wiley and Sons, Inc., 1992).

[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] S. Artmann, F. Göring, J. Harant, D. Rautenbach and I. Schiermeyer, Random procedures for dominating sets in graphs, submitted.

[4] Y. Caro, New results on the independence number (Technical Report. Tel-Aviv University, 1979).

[5] Y. Caro and Y. Roditty, On the vertex-independence number and star decomposition of graphs, Ars Combin. 20 (1985) 167-180.

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

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

[8] F. Göring and J. Harant, On domination in graphs, Discuss. Math. Graph Theory 25 (2005) 7-12, doi: 10.7151/dmgt.1254.

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

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

[11] J. Harant and D. Rautenbach, Domination in bipartite graphs, Discrete Math. 309 (2009) 113-122, doi: 10.1016/j.disc.2007.12.051.

[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., New York, 1998).

[13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs Advanced Topics (Marcel Dekker, Inc., New York, 1998).

[14] C. Payan, Sur le nombre d'absorption d'un graphe simple, (French), Cah. Cent. Étud. Rech. Opér. 17 (1975) 307-317.

[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).