tailieunhanh - Báo cáo toán học: "NEW UPPER BOUNDS ON THE ORDER OF CAGES1"

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: NEW UPPER BOUNDS ON THE ORDER OF CAGES1. | NEW UPPER BOUNDS ON THE ORDER OF CAGES1 F. LAZEBNIK Department of Mathematical Sciences University of Delaware Newark DE 19716 USA fellaz@ V. A. USTIMENKO Department of Mathematics and Mechanics University of Kiev Kiev 252127 Ukraine vau@ A. J. WOLDAR Department of Mathematical Sciences Villanova University Villanova PA 19085 USA woldar@ Submitted August 1 1996 Accepted November 21 1996. Dedicated to Herbert S. Wilf on the occasion of his 65th birthday Abstract Let k 2 and g 3 be integers. A k g -graph is a k-regular graph with girth length of a smallest cycle exactly g. A k g -cage is a k g -graph of minimum order. Let v k g be the order of a k g -cage. The problem of determining v k g is unsolved for most pairs k g and is extremely hard in the general case. It is easy to establish the following lower bounds for v k g v k g 1 k 2 -2 for g odd and v k g 2 1 2 -2 for g even. The best known upper bounds are roughly the squares of the lower bounds. In this paper we establish general upper bounds on v k g which are roughly the 3 2 power of the lower bounds and we provide explicit constructions for such k g -graphs. Mathematical Reviews Subject Numbers 05C35 05C38. Secondary 05D99. 1. Introduction All graphs in this paper are assumed to be simple undirected no loops no multiple edges . Let k 2 and g 3 be integers. A k g -graph is a k-regular 1 This research was supported by NSF grants DMS-9115473 and DMS-9622091. . Woldar was additionally supported by a Villanova University Faculty Research Grant. . Ustimenko was additionally supported in part by INTAS-93-2530 and INTAS-94-3420. F. Lazebnik was additionally supported by a University of Delaware Research Award. 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 4 no. 2 1997 R13 2 graph with girth length of a smallest cycle exactly g. A k g -cage is a k g -graph of minimum order. The problem of determining the order v k g of a k g -cage is unsolved for most pairs k g and is extremely .