Authors: Y. Lin, X. Wang Title: Core index of perfect matching polytope for a 2-connected cubic graph Source: Discussiones Mathematicae Graph Theory Received 04.04.2016, Revised 31.10.2016, Accepted 31.10.2016, doi: 10.7151/dmgt.2001 | |
Abstract: For a 2-connected cubic graph G, the perfect matching polytope P(G) of G contains a special point x^{c}=(\frac{1}{3}, \frac{1}{3},..., \frac{1}{3}). The core index φ(P(G)) of the polytope P(G) is the minimum number of vertices of P(G) whose convex hull contains x^{c}. The Fulkerson's conjecture asserts that every 2-connected cubic graph G has six perfect matchings such that each edge appears in exactly two of them, namely, there are six vertices of P(G) such that x^{c} is the convex combination of them, which implies that φ(P(G))≤ 6. It turns out that the latter assertion in turn implies the Fan-Raspaud conjecture: In every 2-connected cubic graph G, there are three perfect matchings M_{1}, M_{2}, and M_{3} such that M_{1}∩ M_{2}∩ M_{3}=\emptyset. In this paper we prove the Fan-Raspaud conjecture for φ(P(G)) ≤ 12 with certain dimensional conditions. | |
Keywords: Fulkerson's conjecture, Fan-Raspaud conjecture, cubic graph, perfect matching polytope, core index | |
Links: |