On complexity of special maximum matchings constructing

For bipartite graphs the NP-completeness is proved for the problem of existence of maximum matching which removal leads to a graph with given lower(upper) bound for the cardinality of its maximum matching.     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

A note on a conjecture on maximum matching in almost regular graphs

Mkrtchyan, Petrosyan, and Vardanyan made the following conjecture: Every graph G with Δ(G)−δ(G)≤1 has a maximum matching whose unsaturated vertices do not have a common neighbor. We disprove this conjecture.     

On the maximum matchings of regular multigraphs

The lower bounds on the cardinality of the maximum matchings of regular multigraphs are established in terms of the number of vertices, the degree of vertices and the edge-connectivity of a multigraph. The bounds are attained by infinitely many multigraphs, so are best possible.     

最大匹配的路变换图

图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.     

Characterizations of maximum matching graphs of certain types

The maximum matching graph of a graph G is a graph whose vertices are maximum matchings of G and where two maximum matchings are adjacent in if they differ in exactly one edge. In this paper, the author characterizes the graphs whose maximum matching graphs are regular or cycles, and adds trees to the list of known maximum matching graphs.     

Excessive factorizations of bipartite multigraphs

An excessive factorization of a multigraph G is a set F={F₁,F₂,…,F_r} of 1-factors of G whose union is E(G) and, subject to this condition, r is minimum. The integer r is called the excessive index of G and denoted by . We set if an excessive factorization does not exist. Analogously, let m be a fixed positive integer. An excessive[m]-factorization is a set M={M₁,M₂,…,M_k} of matchings of G, all of size m, whose union is E(G) and, subject to this condition, k is minimum. The integer k is denoted by and called the excessive [m]-index of G. Again, we set if an excessive [m]-factorization does not exist. In this paper we shall prove that, for bipartite multigraphs, both the parameters and are computable in polynomial time, and we shall obtain an efficient algorithm for finding an excessive factorization and excessive [m]-factorization, respectively, of any bipartite multigraph.     

Maximum weight edge-constrained matchings

Practical questions arising from (for instance) biological applications can often be expressed as classical optimization problems with specific, new features. We are interested here in the version of the maximum weight matching problem (on a graph G) obtained by (1) defining a set F of pairs of incompatible edges of G and (2) asking that the matching contains at most one edge in each given pair. Such a matching is called an odd matching. The graph T(F)=(V_F,F), where V_F is the set of edges of G occurring in at least one pair of F, is called the trace-graph of G and F.We motivate the introduction of the maximum weight odd-matching (abbreviated as Odd-MWM) problem and study its complexity with respect to two parameters: the type of graph G and the graph class T to which T(F) belongs.Our contribution includes:

•

A proof that Odd-MWM is NP-complete for 3-degree bipartite graphs when T(F) is a matching (i.e. when T is the class of 1-regular graphs), even if the weight function is constant.

•

A proof that Odd-MWM is NP-complete (for 3-degree bipartite graphs as well as for any larger class) if and only if T is a class of graphs with unbounded induced matching. Otherwise, Odd-MWM is polynomial.

•

A (Δ(T(F))+1)-approximate algorithm for Odd-MWM on general graphs. This algorithm becomes a χ(T(F))-approximate algorithm when the graph class T admits a polynomial algorithm for minimum vertex coloring.

     

The maximum genus, matchings and the cycle space of a graph

In this paper we determine the maximum genus of a graph by using the matching number of the intersection graph of a basis of its cycle space. Our result is a common generalization of a theorem of Glukhov [5] and a theorem of Nebeský [15].     

On the approximability of the maximum induced matching problem

In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d−1 for MIM in d-regular graphs, for each d3. We also prove that MIM is APX-complete in d-regular graphs, for each d3.     

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 .     

On edge-disjoint pairs of matchings

For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for |M|/|H|.     

On K_(1,k)-factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n,which partition the set of edges of λKm,n.In this paper,it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n,whenever k is any positive integer,is that(1) m ≤ kn,(2) n ≤ km,(3) km-n ≡ kn-m ≡ 0(mod(k2-1)) and(4) λ(km-n)(kn-m) ≡ 0(mod k(k -1)(k2 -1)(m n)).     

Characterizations of competition multigraphs

The notion of a competition multigraph was introduced by C. A. Anderson, K. F. Jones, J. R. Lundgren, and T. A. McKee [C. A. Anderson, K. F. Jones, J. R. Lundgren, and T. A. McKee: Competition multigraphs and the multicompetition number, Ars Combinatoria 29B (1990) 185-192] as a generalization of the competition graphs of digraphs.In this note, we give a characterization of competition multigraphs of arbitrary digraphs and a characterization of competition multigraphs of loopless digraphs. Moreover, we characterize multigraphs whose multicompetition numbers are at most m, where m is a given nonnegative integer and give characterizations of competition multihypergraphs.     

On K 1,k -factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.     

Perfect matchings after vertex deletions

This paper considers some classes of graphs which are easily seen to have many perfect matchings. Such graphs can be considered robust with respect to the property of having a perfect matching if under vertex deletions (with some mild restrictions), the resulting subgraph continues to have a perfect matching. It is clear that you can destroy the property of having a perfect matching by deleting an odd number of vertices, by upsetting a bipartition or by deleting enough vertices to create an odd component. One class of graphs we consider is the m×m lattice graph (or grid graph) for m even. Matchings in such grid graphs correspond to coverings of an m×m checkerboard by dominoes. If in addition to the easy conditions above, we require that the deleted vertices be apart, the resulting graph has a perfect matching. The second class of graphs we consider is a k-fold product graph consisting of k copies of a given graph G with the ith copy joined to the i+1st copy by a perfect matching joining copies of the same vertex. We show that, apart from some easy restrictions, we can delete any vertices from the kth copy of G and find a perfect matching in the product graph with k suitably large.     

Analyzing local and global properties of multigraphs

The local structure of undirected multigraphs under two random multigraph models is analyzed and compared. The first model generates multigraphs by randomly coupling pairs of stubs according to a fixed degree sequence so that edge assignments to vertex pair sites are dependent. The second model is a simplification that ignores the dependency between the edge assignments. It is investigated when this ignorance is justified so that the simplified model can be used as an approximation, thus facilitating the structural analysis of network data with multiple relations and loops. The comparison is based on the local properties of multigraphs given by marginal distribution of edge multiplicities and some local properties that are aggregations of global properties.     

Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

A matching M is uniquely restricted in a graph G if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself [M.C. Golumbic, T. Hirst, M. Lewenstein, Uniquely restricted matchings, Algorithmica 31 (2001) 139-154]. G is a König-Egerváry graph provided α(G)+μ(G)=|V(G)| [R.W. Deming, Independence numbers of graphs—an extension of the König-Egerváry theorem, Discrete Math. 27 (1979) 23-33; F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, J. Combin. Theory Ser. B 27 (1979) 228-229], where μ(G) is the size of a maximum matching and α(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G, and we write S∈Ψ(G), if S is a maximum stable set of the subgraph spanned by S∪N(S), where N(S) is the neighborhood of S. Nemhauser and Trotter [Vertex packings: structural properties and algorithms, Math. Programming 8 (1975) 232-248], proved that any S∈Ψ(G) is a subset of a maximum stable set of G. In [V.E. Levit, E. Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Appl. Math. 132 (2003) 163-174] we have proved that for a bipartite graph G,Ψ(G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. In this paper we demonstrate that if G is a triangle-free graph, then Ψ(G) is a greedoid if and only if all its maximum matchings are uniquely restricted and for any S∈Ψ(G), the subgraph spanned by S∪N(S) is a König-Egerváry graph.