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í toán học quốc tế đề tài: TIGHT UPPER BOUNDS FOR THE DOMINATION NUMBERS OF GRAPHS WITH GIVEN ORDER AND MINIMUM DEGREE. | TIGHT UPPER BOUNDS FOR THE DOMINATION NUMBERS OF GRAPHS WITH GIVEN ORDER AND MINIMUM DEGREE W. Edwin Clark UNiVERSiTy OF South Florida Tampa fl 33620-5700 eclark@ and Larry A. Dunning Bowling Green State UNiVERSiTy Bowling Green oh 43403-0214 dunning@ Submitted June 2 1997 Accepted October 27 1997 Abstract. Let Y n Ỗ denote the maximum possible domination number of a graph with n vertices and minimum degree Ỗ. Using known results we determine y n Ỗ for Ỗ 0 1 2 3 n Ỗ 1 and for all n Ỗ where Ỗ n k and n is sufficiently large relative to k. We also obtain Y n Ỗ for all remaining values of n Ỗ when n 14 and all but 6 values of n Ỗ when n 15 or 16. 1. Introduction We denote the domination number of a graph G by 7 G . By an n Ỗ -graph we mean a graph with n vertices and minimum degree Ỗ. Let Y n Ỗ be the maximum of y G where G is an n Ỗ -graph. Using known results 3 7 8 9 one easily finds the exact values of Y n Ỗ when Ỗ 0 1 2 3. It is also fairly easy to obtain Y n Ỗ when Ỗ n k for n sufficiently large relative to k. By various methods we also find Y n Ỗ for all remaining values of n Ỗ when n 14 and all but 6 values of n Ỗ when n 15 and 16. Many values can be established using the upper bounds in 2 together with examples found by computer search or ad hoc techniques. In a number of cases we have used Brendan McKay s program makeg to 1991 Mathematics Subject Classification. 05C35. Key words and phrases. graph domination number upper bounds minimum degree. m 11 4 . . ế m w THE ELECTRONIC JOURNAL OF COMBINATORICS 4 1997 R26 2 generate all nonisomorphic n S -graphs 6 while checking the domination numbers using a simple recursive depth-hrst search. Our results give support to the the natural conjecture that Y n S is attained by an n S -graph with the minimum number of edges that is by a regular graph if nS is even or by a graph with degree sequence S 1 S S . S if nS is odd. We are able to verify the conjecture for all the cases mentioned above where we
