Core Index of Perfect Matching Polytope for a 2-Connected Cubic Graph

• Autorzy: Xiumei Wang , Yixun Lin
• Języki publikacji: EN

Abstrakty

EN

For a 2-connected cubic graph G, the perfect matching polytope P(G) of G contains a special point [...] xc=(13,13,…,13) $x^c = \left( {{1 \over 3},{1 \over 3}, \ldots ,{1 \over 3}} \right)$ . The core index ϕ(P(G)) of the polytope P(G) is the minimum number of vertices of P(G) whose convex hull contains xc. 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 xc 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 M1, M2, and M3 such that M1 ∩ M2 ∩ M3 = ∅. In this paper we prove the Fan-Raspaud conjecture for ϕ(P(G)) ≤ 12 with certain dimensional conditions.

Słowa kluczowe

EN

Fulkerson’s conjecture; Fan-Raspaud conjecture; cubic graph; perfect matching polytope; core index

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 38
• Numer: 1
• Strony: 189-201

Daty

wydano

2018-02-01

otrzymano

2016-04-04

poprawiono

2016-10-31

zaakceptowano

2016-10-31

online

2017-12-30

Twórcy

autor

Xiumei Wang

• , , ,,

autor

Yixun Lin

• , , ,

Identyfikatory

DOI

10.7151/dmgt.2001