Matchings in regular graphs

We consider k-regular graphs with specified edge connectivity and show how some classical theorems and some new results concerning the existence of matchings in such graphs can be proved by using the polyhedral characterization of Edmonds. In addition, we show that lower bounds of Lovász and Plummer on the number of perfect matchings in bicritical graphs can be improved for cubic bicritical graphs.     

Constructive proof of deficiency theorem of (g, f)-factor

Berge (1958) gave a formula for computing the deficiency of maximum matchings of a graph. More generally, Lovász obtained a deficiency formula of (g, f)-optimal graphs and consequently a criterion for the existence of (g, f)-factors. Moreover, Lovász proved that there is one of these decompositions which is “canonical“ in a sense. In this paper, we present a short constructive proof for the deficiency formula of (g, f)-optimal graphs, and the proof implies an efficient algorithm of time complexity O(g(V)|E|) for computing the deficiency. Furthermore, this proof implies this canonical decomposition via efficient algorithms (i.e., in polynomial time).     

Matchings in graphs II

Proofs are given of theorems of Lovász and Brualdi on the existence in a finite simple graph of matchings required to meet vertices in a given set A of vertices. An alternating chain condition is obtained for a maximum matching to meet all the vertices in A.     

Forbidden subgraphs and the König–Egerváry property

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König–Egerváry property  if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász’s result to a characterization of all graphs having the König–Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König–Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs.     

König–Egerváry Graphs are Non-Edmonds

König–Egerváry graphs are those whose maximum matchings are equicardinal to their minimum-order coverings by vertices. Edmonds (J Res Nat Bur Standards Sect B 69B:125–130, 1965) characterized the perfect matching polytope of a graph G = (V, E) as the set of nonnegative vectors ${{\bf{x}}\in\mathbb R^E}K?nig–Egerváry graphs are those whose maximum matchings are equicardinal to their minimum-order coverings by vertices. Edmonds (J Res Nat Bur Standards Sect B 69B:125–130, 1965) characterized the perfect matching polytope of a graph G = (V, E) as the set of nonnegative vectors x ? \mathbb R^E{{\bf{x}}\in\mathbb R^E} satisfying two families of constraints: ‘vertex saturation’ and ‘blossom’. Graphs for which the latter constraints are implied by the former are termed non-Edmonds. This note presents two proofs—one combinatorial, one algorithmic—of its title’s assertion. Neither proof relies on the characterization of non-Edmonds graphs due to de Carvalho et al. (J Combin Theory Ser B 92:319–324, 2004).     

Forbidden subgraphs and the Kőnig property

A graph has the Kőnig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Kőnig property by forbidden subgraphs, restricted to graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovászʼs result to a characterization of all graphs having the Kőnig property in terms of forbidden configurations (certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the Kőnig property in terms of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. As a consequence of our characterization of graphs with the Kőnig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs.     

Matching preclusion and conditional matching preclusion for regular interconnection networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks.     

Cubic bridgeless graphs have more than a linear number of perfect matchings

Lovász and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve (1979), and for planar graphs by Chudnovsky and Seymour (2008). In this paper, we provide the first superlinear bound in the general case.     

Ear Decompositions of Matching Covered Graphs

G different from and has at least Δ edge-disjoint removable ears, where Δ is the maximum degree of G. This shows that any matching covered graph G has at least Δ! different ear decompositions, and thus is a generalization of the fundamental theorem of Lovász and Plummer establishing the existence of ear decompositions. We also show that every brick G different from and has Δ− 2 edges, each of which is a removable edge in G, that is, an edge whose deletion from G results in a matching covered graph. This generalizes a well-known theorem of Lovász. We also give a simple proof of another theorem due to Lovász which says that every nonbipartite matching covered graph has a canonical ear decomposition, that is, one in which either the third graph in the sequence is an odd-subdivision of or the fourth graph in the sequence is an odd-subdivision of . Our method in fact shows that every nonbipartite matching covered graph has a canonical ear decomposition which is optimal, that is one which has as few double ears as possible. Most of these results appear in the Ph. D. thesis of the first author [1], written under the supervision of the second author. Received: November 3, 1997     

Ear decompositions of join covered graphs

Join covered graphs are ±1-weighted graphs, without negative circuits, in which every edge lies in a zero-weight circuit. Join covered graphs are a natural generalization of matching covered graphs. Many important properties of matching covered graphs have been generalized to join covered graphs. In this paper, we generalize Lovász and Plummerʼs ear decomposition theorem of matching covered graphs to join covered graphs.     

Copositive programming motivated bounds on the stability and the chromatic numbers

The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the chromatic number of G, which is shown to be equal to the fractional chromatic number of G. Solving copositive programs is NP-hard. This motivates the study of tractable approximations of the copositive cone. We investigate the Parrilo hierarchy to approximate this cone and provide computational simplifications for the approximation of the chromatic number of vertex transitive graphs. We provide some computational results indicating that the Lovász theta number can be strengthened significantly toward the fractional chromatic number of G on some Hamming graphs. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

Forcing matching numbers of fullerene graphs

The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.     

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     

Computing clique and chromatic number of circular-perfect graphs in polynomial time

A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function.     

On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs

A main result in combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 1981). The circular-clique and circular-chromatic number are well-studied refinements of these graph parameters, and circular-perfect graphs form the corresponding superclass of perfect graphs. So far, it is unknown whether the (weighted) circular-clique and circular-chromatic number of a circular-perfect graph are computable in polynomial time. In this paper, we show the polynomial time computability of these two graph parameters for some super-classes of perfect graphs with the help of polyhedral arguments.     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

Almost integral polyhedra related to certain combinatorial optimization problems

The notion of an almost integral polyhedron is introduced and used to obtain a new proof of the characterization of perfect zero-one matrices which relies only on standard arguments from linear algebra and convexity. The characterization of perfect zero-one matrices in terms of forbidden submatrices is then used to derived the perfect-graph theorem due to Fulkerson and Lovász. Furthermore, a characterization of antiblocking pairs of zero-one matrices by means of a strengthened version of the max-max inequality due to Fulkerson is obtained which entails Lovász's recent characterization of perfect graphs.     

Unicycle graphs and uniquely restricted maximum matchings

A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. G is a unicycle graph if it owns only one cycle. Golumbic, Hirst and Lewenstein observed that for a tree or a graph with only odd cycles the size of a maximum uniquely restricted matching is equal to the matching number of the graph. In this paper we characterize unicycle graphs enjoying this equality. Moreover, we describe unicycle graphs with only uniquely restricted maximum matchings. Using these findings, we show that unicycle graphs having only uniquely restricted maximum matchings can be recognized in polynomial time.     

Lift and project relaxations for the matching and related polytopes

We compare lift and project methods given by Lovász and Schrijver (the N₊ and N procedures) and by Balas, Ceria and Cornuéjols (the disjunctive procedure) when working on the matching, perfect matching and covering polytopes. When the underlying graph is the complete graph of n=2s+1 nodes we obtain that the disjunctive index for all problems is s², the N₊-index for the matching and perfect matching problems is s (extending a result by Stephen and Tunçel), the N-index for the perfect matching problem is s, and the N₊ and N indices for the covering problem and the N-index for the matching problem are strictly greater than s.