Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của 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, II. | Tight Upper Bounds for the Domination Numbers of Graphs with Given Order and Minimum Degree II W. Edwin Clark and Stephen Suen eclark@ suen@ Department of Mathematics University of South Florida Tampa FL 33620-5700 USA Larry A. Dunning dunningk@ Department of Computer Science Bowling Green State University Bowling Green OH 43403-0214 USA Submitted August 12 2000 Accepted November 6 2000 Abstract Let Y n Ỗ denote the largest possible domination number for a graph of order n and minimum degree Ỗ. This paper is concerned with the behavior of the right side of the sequence n Y n 0 Y n 1 Y n n 1 1. We set ỗk n max ỗ I Y n Ỗ kg k 1. Our main result is that for any fixed k 2 there is a constant ck such that for sufficiently large n n ckn k V k ỗk 1 n n n k 1 k. The lower bound is obtained by use of circulant graphs. We also show that for n sufficiently large relative to k Y n ỗk n k. The case k 3 is examined in further detail. The existence of circulant graphs with domination number greater than 2 is related to a kind of difference set in Zn. 2000 Mathematics Subject Classifications Primary 05C69 Secondary 05C35 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R58 2 n s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 1 3 1 1 4 2 2 1 5 2 2 1 1 6 3 2 2 2 1 7 3 3 2 2 1 1 8 4 4 3 2 2 2 1 9 4 4 3 3 2 2 1 1 10 5 4 3 3 2 2 2 2 1 11 5 5 4 3 3 3 2 2 1 1 12 6 6 4 4 3 3 2 2 2 2 1 13 6 6 4 4 3 3 3 2 2 2 1 1 14 7 6 5 4 4 3 3 3 2 2 2 2 1 15 7 7 5 5 4 4 3 3 t3 2 2 2 1 1 16 8 8 6 5 5 4 4 3 t3 t3 2 2 2 2 1 Table 1 Values of Y n s for 1 n 16. Entries marked with asterisks are unknown. For these cases the best known upper bounds for Y n s are given. Entries determined in Section 5 are marked by daggers. 1 Introduction As in 2 we say that a simple graph r with n vertices and minimum degree s is an n s -graph and we define Y n s max Y r I r is an n s -graph where Y r denotes the domination number of r. We are interested in the behavior of the right side of the .
