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

Discussiones Mathematicae Graph Theory (2018)

- Volume: 38, Issue: 1, page 189-201
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topXiumei Wang, and Yixun Lin. "Core Index of Perfect Matching Polytope for a 2-Connected Cubic Graph." Discussiones Mathematicae Graph Theory 38.1 (2018): 189-201. <http://eudml.org/doc/288521>.

@article{XiumeiWang2018,

abstract = {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.},

author = {Xiumei Wang, Yixun Lin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Fulkerson’s conjecture; Fan-Raspaud conjecture; cubic graph; perfect matching polytope; core index},

language = {eng},

number = {1},

pages = {189-201},

title = {Core Index of Perfect Matching Polytope for a 2-Connected Cubic Graph},

url = {http://eudml.org/doc/288521},

volume = {38},

year = {2018},

}

TY - JOUR

AU - Xiumei Wang

AU - Yixun Lin

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

JO - Discussiones Mathematicae Graph Theory

PY - 2018

VL - 38

IS - 1

SP - 189

EP - 201

AB - 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.

LA - eng

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

UR - http://eudml.org/doc/288521

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.