tailieunhanh - Báo cáo toán học: TIGHT UPPER BOUNDS FOR THE DOMINATION NUMBERS OF GRAPHS WITH GIVEN ORDER AND MINIMUM DEGREE

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