Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A note on pm-compact bipartite graphs

100%

Liu J., Wang X.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 2

409-413

A graph is called perfect matching compact (briefly, PM-compact), if its perfect matching graph is complete. Matching-covered PM-compact bipartite graphs have been characterized. In this paper, we show that any PM-compact bipartite graph G with δ (G) ≥ 2 has an ear decomposition such that each graph in the decomposition sequence is also PM-compact, which implies that G is matching-covered

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

100%

Wang X., Lin Y.

Discussiones Mathematicae Graph Theory

2017

tom 38

nr 1

189-201

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Wang X.

1 Lin Y.

1 Liu J.

1 2018

1 2014

Wyniki wyszukiwania

A note on pm-compact bipartite graphs

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