PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 38 | 1 | 189-201
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
38
Numer
1
Strony
189-201
Opis fizyczny
Daty
wydano
2018-02-01
otrzymano
2016-04-04
poprawiono
2016-10-31
zaakceptowano
2016-10-31
online
2017-12-30
Twórcy
autor
autor
  • , , ,
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_2001
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.