Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Random Procedures for Dominating Sets in Graphs. | Random Procedures for Dominating Sets in Graphs Sarah Artmann Institut fur Mathematik TU Ilmenau D-98684 Ilmenau Germany Frank Goring Fakultat fur Mathematik TU Chemnitz D-09107 Chemnitz Germany Jochen Harant Institut fuur Mathematik TU Ilmenau D-98684 Ilmenau Germany j Dieter Rautenbach Institut fur Optimierung und Operations Research Universitat Ulm D-89069 Ulm Germany Ingo Schiermeyer Institut fur Diskrete Mathematik und Algebra TU Bergakademie Freiberg D-09596 Freiberg Germany Submitted Jun 26 2008 Accepted Jul 13 2010 Published Jul 20 2010 Mathematics Subject Classifications 05C69 Abstract We present and analyze some random procedures for the construction of small dominating sets in graphs. Several upper bounds for the domination number of a graph are derived from these procedures. Keywords domination independence probabilistic method THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R102 1 1 Introduction We consider finite simple and undirected graphs G V E with vertex set V edge set E order n V and size m E . The neighbourhood of a vertex u G V in the graph G is the set NG u v G V uv G E and the closed neighbourhood of u in G is NG u NG u u u . The degree of u in G is the number dG u NG u of its neighbours. For a set U G V let NG U uu U NG u and NG U NG U U. A set of vertices D G V of G is dominating if every vertex in V D has a neighbour in D. The minimum cardinality of a dominating set is the domination number y G of G. A set of vertices I G V of G is independent if no two vertices in I are adjacent. The maximum cardinality of an independent set is the independence number a G of G. Dominating and independent sets are among the most well-studied graph theoretical objects. The literature on this subject has been surveyed and detailed in the two books by Haynes Hedetniemi and Slater 7 8 . Natural .
