tailieunhanh - Báo cáo toán học: "All regular multigraphs of even order and high degree are 1-factorable"

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: All regular multigraphs of even order and high degree are 1-factorable. | All regular multigraphs of even order and high degree are 1-factorable Michael J. Plantholt Shailesh K. Tipnis Department of Mathematics Illinois State University Normal IL 61790-4520 USA mikep@ tipnis@ Submitted March 13 2001 Accepted December 8 2001. Mathematical Reviews Subject Classification 2000 05C15 05C70. Abstract Plantholt and Tipnis 1991 proved that for any even integer r a regular multigraph G with even order n multiplicity p G r and degree high relative to n and r is 1-factorable. Here we extend this result to include the case when r is any odd integer. Haggkvist and Perkovic and Reed 1997 proved that the One-factorization Conjecture for simple graphs is asymptotically true. Our techniques yield an extension of this asymptotic result on simple graphs to a corresponding asymptotic result on multigraphs. 1 Introduction Let G be a multigraph with vertex set V G and edge set E G . We denote the maximum degree of G by A G the minimum degree of G by 8 G and the multiplicity of G that is the maximum number of parallel edges between any pair of vertices of G by ụ G . G is said to be simple if p G 1. We say that G is 1-factorable if the edges of G can be partitioned into 1-factors of G. We denote by simp G the simple graph underlying G . simp G is the graph obtained by replacing all edges of G with multiplicity greater than one by single edges. In this paper a decomposition of G into edge-disjoint subgraphs Hi H2 . Hk of G means a partition of E G into the union of the edge sets of Hl H2 . Hk and we abuse the notation and write G Hl u H2 u . u Hk instead of E G E Hl u E H2 u . u E Hk . The reader is referred to Bondy and Murty 2 for all terminology undefined in this paper. The following long-standing conjecture whose THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R41 1 origin is unclear claims that any regular simple graph of even order and with degree at least half the number of vertices is 1-factorizable see 10 . .