- Tytuł:
- Core Index of Perfect Matching Polytope for a 2-Connected Cubic Graph
- Autorzy:
-
Wang, Xiumei
Lin, Yixun - Powiązania:
- https://bibliotekanauki.pl/articles/31343794.pdf
- Data publikacji:
- 2018-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Fulkerson’s conjecture
Fan-Raspaud conjecture
cubic graph
perfect matching polytope
core index - Opis:
- For a 2-connected cubic graph $G$, the perfect matching polytope $P(G)$ of $G$ contains a special point \( x^c = ( \tfrac{1}{3},\tfrac{1}{3},…,\tfrac{1}{3}) \). The core index $ \phi(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 $ \phi(P(G)) \le 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 \cap M_2 \cap M_3 = \emptyset $. In this paper we prove the Fan-Raspaud conjecture for $ \phi(P(G)) \le 12 $ with certain dimensional conditions.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 189-201
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł