Core index of perfect matching polytope for a 2-connected cubic graph
Yixun Lin, Xiumei Wang · Discussiones Mathematicae Graph Theory · 2017
For a 2-connected cubic graph G, the perfect matching polytope P (G) of G contains a special point x c = 1 3 , 1 3 , . . . , 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 = . In this paper we prove the Fan-Raspaud conjecture for (P (G)) 12 with certain dimensional conditions.