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: On the number of perfect matchings and Hamilton cycles in -regular non-bipartite graphs. | On the number of perfect matchings and Hamilton cycles in c-regular non-bipartite graphs Alan Frieze Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA15213 USA alan@ Submitted July 4 2000 Accepted November 19 2000 Abstract A graph G V E on n vertices is super e-regular if i all vertices have degree in the range d e n d e n dn being the average degree and ii for every pair of disjoint sets S T c V S TI en e S T is in the range d e S TI d e S T . We show that the number of perfect matchings lies in the range d 2ep n d 2ep nr where V n and the number of Hamilton cycles lies in the range d 2e nn d 2e nn . 1 Introduction Let G V E be a graph with V n. Let 0 d 1 and c 0 be constants independent of n where c is assumed to be small compared with d. We assume that the density of G is d . E n d. Suppose that the following two conditions hold If dG denotes vertex degree in G then d c n dG v d c n for all v E V. 1 Supported in part by NSF Grant CCR9818411 Mathematics Subject Classification 1991 primary 05C50 05C70 secondary 05C80 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R57 2 If for S T c V S n T we let e S T denote the number of edges of G with one end in S and the other in T and d S T s Tj then d S T - d 6 for all S T c V S n T SI T en. 2 A graph satisfying 1 2 said to be super e-regular. We assume that n 2u is even. Let m G denote the number of perfect matchings in G and let h G denote the number of Hamilton cycles in G. In this paper we prove Theorem 1 If 6 is sufficiently small and n is sufficiently large then a n n d - 2e ÃÃ m G d 2e ỹ ỹ. b d - 2e nn h G d 2e nn . In both cases the bounds are close to the expected number of in the random graph Gn d- The results here are strongly related to the result of Alon Rodl and Rucinski 2 . They considered bipartite graphs H with vertex partition A B where A B n. Assuming 1 and 2 for S c A and T c B they proved Theorem 2 2 d 2e nn m G d 2e nn . Michael Krivelevich has made .
