Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the Number of Matchings in Regular Graphs. | On the Number of Matchings in Regular Graphs S. Friedland E. Kropy and K. Markstromz Submitted Jan 18 2008 Accepted Aug 22 2008 Published Aug 31 2008 Mathematics Subject Classification 05A15 05A16 05C70 05C80 05C88 82B20 Abstract For the set of graphs with a given degree sequence consisting of any number of 20s and 10s and its subset of bipartite graphs we characterize the optimal graphs who maximize and minimize the number of m-matchings. We End the expected value of the number of m-matchings of r-regular bipartite graphs on 2n vertices with respect to the two standard measures. We state and discuss the conjectured upper and lower bounds for m-matchings in r-regular bipartite graphs on 2n vertices and their asymptotic versions for infinite r-regular bipartite graphs. We prove these conjectures for 2-regular bipartite graphs and for m-matchings with m 4. Keywords and phrases Partial matching and asymptotic growth of average matchings for r-regular bipartite graphs asymptotic matching conjectures. 1 Introduction Let G V E be an undirected graph with the set of vertices V and the set of edges E. An m-matching M c E is a set of m distinct edges in E such that no two edges have a common vertex. We say that M covers U c V U 2 M if the set of vertices incident to M is U. Denote by m G the number of m-matchings in G. If V is even then t-matching is called a perfect matching or 1-factor of G and d r G is the number of 1-factors in G. For an infinite graph G V E a match M c E is a match of density Department of Mathematics Statistics and Computer Science University of Illinois at Chicago Chicago Illinois 60607-7045 USA friedlan@ . yDepartment of Mathematics Statistics and Computer Science University of Illinois at Chicago Chicago Illinois 60607-7045 USA ekrop1@ . zDepartment of Mathematics and Mathematical Statistics UmeảUniversity SE-901 87 Umeả Sweden THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R110 1 p 2 0 1 if the proportion of vertices in V .
