The graph of perfect matching polytope and an extreme problem

For graph G, its perfect matching polytope Poly(G) is the convex hull of incidence vectors of perfect matchings of G. The graph corresponding to the skeleton of Poly(G) is called the perfect matching graph of G, and denoted by PM(G). It is known that PM(G) is either a hypercube or hamilton connected [D.J. Naddef, W.R. Pulleyblank, Hamiltonicity and combinatorial polyhedra, J. Combin. Theory Ser. B 31 (1981) 297-312; D.J. Naddef, W.R. Pulleyblank, Hamiltonicity in (0-1)-polytope, J. Combin. Theory Ser. B 37 (1984) 41-52]. In this paper, we give a sharp upper bound of the number of lines for the graphs G whose PM(G) is bipartite in terms of sizes of elementary components of G and the order of G, respectively. Moreover, the corresponding extremal graphs are constructed.     

Characterization of stable matchings as extreme points of a polytope

The purpose of this paper is to extend a modified version of a recent result of Vande Vate (1989) which characterizes stable matchings as the extreme points of a certain polytope. Our proofs are simpler and more transparent than those of Vande Vate.     

On perfect matchings in matching covered graphs

A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and .     

Smallest close to regular bipartite graphs without an almost perfect matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.     

The equipartition polytope. II: Valid inequalities and facets

Theequipartition problem is defined as follows: given a graphG = (V, E) and edge weightsc _e , partition the setV into two sets of 1/2|V| and 1/2|V| nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized.Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we describe some facet inducing inequalities of this polytope.Partial support of NSF grants DMS 8606188 and ECS 8800281.This work was done while these two authors visited IASI, Rome, in Spring 1987.     

Lift-and-project cuts and perfect graphs

We analyze the application of lift-and-project to the clique relaxation of the stable set polytope. We characterize all the inequalities that can be generated through the application of the lift-and-project procedure, introduce the concept of 1-perfection and prove its equivalence to minimal imperfection. This characterization of inequalities and minimal imperfection leads to a generalization of the Perfect Graph Theorem of Lovász, as proved by Aguilera, Escalante and Nasini [1].Mathematics Subject Classification:05C17, 90C57     

The equipartition polytope. I: Formulations,dimension and basic facets

The following basic clustering problem arises in different domains, ranging from physics, statistics and Boolean function minimization.Given a graphG = (V, E) and edge weightsc _e , partition the setV into two sets of 1/2|V| and 1/2|V| nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized.Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we give some integer programming formulations of the equicut problem, study the dimension of the equicut polytope and describe some basic classes of facet-inducing inequalities forQ(G). Partial support of NSF grants DMS 8606188 and ECS 8800281.This work was done while these two authors visited IASI, Rome, in Spring 1987.     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Minimum codegree condition for perfect matchings in k-partite k-graphs

Let be a -partite -graph with vertices in each partition class, and let denote the minimum codegree of . We characterize those with and with no perfect matching. As a consequence, we give an affirmative answer to the following question of Rödl and Ruciński: if is even or , does imply that has a perfect matching? We also give an example indicating that it is not sufficient to impose this degree bound on only two types of -sets.     

Exponentially many perfect matchings in cubic graphs

We show that every cubic bridgeless graph G has at least ²|V(G)|/3656 perfect matchings. This confirms an old conjecture of Lovász and Plummer.     

Disjoint perfect matchings in 3‐uniform hypergraphs

For a hypergraph H, let denote the minimum vertex degree in H. Kühn, Osthus, and Treglown proved that, for any sufficiently large integer n with , if H is a 3‐uniform hypergraph with order n and then H has a perfect matching, and this bound on is best possible. In this article, we show that under the same conditions, H contains at least pairwise disjoint perfect matchings, and this bound is sharp.     

Gear composition and the stable set polytope

We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of when G is claw-free.