Upper Bounds for the Domination Number of a Graph

. This paper compares several upper bounds based on the degree sequence of a graph G for the domination number fl(G). In particular, we show that the domination number of a graph G with n vertices and minimum degree ffi is at most (1 \Gamma S ffi )n where S k = Q k+1 i=1 ik 1+ik . This supercedes Arnautov's bound [4] fl(G) n ffi+1 H ffi+1 where H k = 1 + 1 2 + 1 3 + \Delta \Delta \Delta + 1 k , and the bound fl(G) 1 ffi+1 (1 + ln(ffi + 1))n in Alon and Spencer [1]. We also improve our upper bound slightly in the case of regular graphs. Keywords: graph, domination number, upper bounds AMS Classification: 05C35. 1 Introduction Here G = (V; E) denotes a (simple) graph of order p and minimum degree ffi. We denote the vertices of G by x 1 , x 2 , . . . , x p and set d i = deg(x i ). Let N(x) be the set of vertices adjacent to vertex x and let N [x] = N(x) [ fxg. For a subset X of V , the set of elements in V covered by X is the set N [X] = [ x2X N [x]: If N [X] = V ..