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

Xiumei Wang; Yixun Lin

Discussiones Mathematicae Graph Theory (2018)

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

Abstract

top
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 = 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 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.

How to cite

top

Xiumei 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.