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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Perfect Matchings in Claw-free Cubic Graphs. | Perfect Matchings in Claw-free Cubic Graphs Sang-il Oum Department of Mathematical Sciences KAIST Daejeon 305-701 Republic of Korea sangil@ Submitted Nov 9 2009 Accepted Mar 7 2011 Published Mar 24 2011 Mathematics Subject Classification 05C70 Abstract Lovasz and Plummer conjectured that there exists a fixed positive constant c such that every cubic n-vertex graph with no cutedge has at least 2cn perfect matchings. Their conjecture has been verified for bipartite graphs by Voorhoeve and planar graphs by Chudnovsky and Seymour. We prove that every claw-free cubic n-vertex graph with no cutedge has more than 2n 12 perfect matchings thus verifying the conjecture for claw-free graphs. 1 Introduction A graph is claw-free if it has no induced subgraph isomorphic to K1 3. A graph is cubic if every vertex has exactly three incident edges. A well-known classical theorem of Petersen 10 states that every cubic graph with no cutedge has a perfect matching. Sumner 11 and Las Vergnas 7 independently showed that every connected claw-free graph with even number of vertices has a perfect matching. Both theorems imply that every claw-free cubic graph with no cutedge has at least one perfect matching. In 1970s Lovasz and Plummer conjectured that every cubic graph with no cutedge has exponentially many perfect matchings see 8 Conjecture . The best lower bound has been obtained by Esperet Kardos and Kral 6 . They showed that the number of perfect matchings in a sufficiently large cubic graph with no cutedge always exceeds any fixed linear function in the number of vertices. So far the conjecture is known to be true for bipartite graphs and planar graphs. For bipartite graphs Voorhoeve 12 proved that every bipartite cubic n-vertex graph has at least 6 4 3 n 2-3 perfect matchings. Recently Chudnovsky and Seymour 2 proved that every planar cubic n-vertex graph with no cutedge has at least 2n 655978752 perfect matchings. Supported by Basic Science Research Program through .
