Rainbow matchings in bipartite multigraphs

Suppose that k is a non-negative integer and a bipartite multigraph G is the union of

$$\begin{aligned} N=\left\lfloor \frac{k+2}{k+1}n\right\rfloor -(k+1) \end{aligned}$$

matchings \(M_1,\dots ,M_N\), each of size n. We show that G has a rainbow matching of size \(n-k\), i.e. a matching of size \(n-k\) with all edges coming from different \(M_i\)’s. Several choices of the parameter k relate to known results and conjectures.

     

Decomposition of bipartite multigraphs into matchings

Summary In this paper we show that a bipartite multigraphG in which no vertex is adjacent to more thann edges may be decomposed into any numbern ^*n of matchings in such a way that the number of edges in each of these matchings differ from one another by at most one unit. When the two sets of verticesX and¯X ofG are partitioned into subsetsX _i and¯X _j respectively, we give conditions for the existence of a decomposition ofG inton ^*n matchings such that each matching contains at most _i edges adjacent to vertices inX _i and at most _j edges adjacent to vertices in¯X _j .There are many practical problems of scheduling with resource limitations for which such decompositions of a bipartite graph are required; some examples are given.

---

Zusammenfassung Es wird gezeigt, daß ein bipartiter MultigraphG, in dem in keinem Knoten mehr alsn Kanten zusammenstoßen, in eine beliebige Zahln ^*n von matchings dekomponiert werden kann, und zwar derart, daß die Zahl der Kanten in jedem dieser matchings untereinander um höchstens eins differiert. Mit dem Aufteilen der beiden KnotenmengenX und ¯X vonG in UntermengenX _i und¯X _j werden Bedingungen für die Existenz einer Dekomposition vonG inn ^* n matchings angegeben, wobei jedes matching höchstens _i ( _j ) Kanten enthält, die in den KnotenX _i (bzw.¯X _j ) zusammenstoßen.Es gibt viele praktische Planungsprobleme mit beschränkten Ressourcen, für die solche Dekompositionen von bipartiten Graphen verlangt werden; einige Beispiele werden angeführt.

---

---

This work was supported by a grant from the National Research Council of Canada.     

On the signed star domination number of regular multigraphs

Let $G$ be a graph with the vertex set $V(G)$ and the edge set $E(G)$ . A function $f: E(G)\longrightarrow \{-1, 1\}$ is said to be a signed star dominating function of $G$ if $\sum _{e \in E_G(v)}f (e)\ge 1 $ , for every $v \in V(G)$ , where $E_G(v) = \{uv\in E(G)\,|\,u \in V (G)\}$ . The minimum values of $\sum _{e \in E_G(v)}f (e)$ , taken over all signed star dominating functions $f$ on $G$ , is called the signed star domination number of $G$ and denoted by $\gamma _{SS}(G)$ . In this paper we determine the signed star domination number of regular multigraphs.     

Factorization of regular multigraphs into regular graphs

A regular multigraph with maximum multiplicity r and degree rs cannot always be factored into r s-regular simple graphs. It is shown, however, that under general conditions a similar factorization can be achieved if we first allow the addition or deletion of a relatively small number of hamilton cycles. Based on this result, we give extensions of some known factorization results on simple graphs to new results on multigraphs. © 1995 John Wiley & Sons, Inc.     

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.     

On induced matchings as star complements in regular graphs

We determine all the finite regular graphs which have an induced matching or a cocktail party graph as a star complement.     

Achieving maximum chromatic index in multigraphs

Let G be a multigraph with maximum degree Δ and maximum edge multiplicity μ. Vizing’s Theorem says that the chromatic index of G is at most Δ+μ. If G is bipartite its chromatic index is well known to be exactly Δ. Otherwise G contains an odd cycle and, by a theorem of Goldberg, its chromatic index is at most , where g_o denotes odd-girth. Here we prove that a connected G achieves Goldberg’s upper bound if and only if G=μC_go and (g_o−1)∣2(μ−1). The question of whether or not G achieves Vizing’s upper bound is NP-hard for μ=1, but for μ≥2 we have reason to believe that this may be answerable in polynomial time. We prove that, with the exception of μK₃, every connected G with μ≥2 which achieves Vizing’s upper bound must contain a specific dense subgraph on five vertices. Additionally, if Δ≤μ², we prove that G must contain K₅, so G must be nonplanar. These results regarding Vizing’s upper bound extend work by Kierstead, whose proof technique influences us greatly here.     

Largest regular multigraphs with three distinct eigenvalues

We deal with connected $k$-regular multigraphs of order $n$ that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given $k$. For $k=2,3,7$, the Moore graphs are largest. For $k\ne 2,3,7,57$, we show an upper bound $n\le k^2?k+1$, with equality if and only if there exists a finite projective plane of order $k?1$ that admits a polarity.     

无环多重图的最大亏格的下界

The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous known results. Thus, a picture of the lower bounds on the maximum genus of loopless multigraphs is presented.     

Perfect matchings in regular bipartite graphs

P. Hall, [2], gave necessary and sufficient conditions for a bipartite graph to have a perfect matching. Koning, [3], proved that such a graph can be decomposed intok edge-disjoint perfect matchings if and only if it isk-regular. It immediately follows that in ak-regular bipartite graphG, the deletion of any setS of at mostk – 1 edges leaves intact one of those perfect matchings. However, it is not known what happens if we delete more thank – 1 edges. In this paper we give sufficient conditions so that by deleting a setS ofk + r edgesr 0, stillG – S has a perfect matching. Furthermore we prove that our result, in some sense, is best possible.     

Nearly perfect matchings in regular simple hypergraphs

For every fixedk≥3 there exists a constantc _k with the following property. LetH be ak-uniform,D-regular hypergraph onN vertices, in which no two edges contain more than one common vertex. Ifk>3 thenH contains a matching covering all vertices but at mostc _k ND ^−1/(k−1). Ifk=3, thenH contains a matching covering all vertices but at mostc ₃ ND ^−1/2ln^3/2 D. This improves previous estimates and implies, for example, that any Steiner Triple System onN vertices contains a matching covering all vertices but at mostO(N ^1/2ln^3/2 N), improving results by various authors. Research supported in part by a USA-Israel BSF grant. Research supported in part by a USA-Israel BSF Grant.     

Rank of maximum matchings in a graph

The matching polytope is the convex hull of the incidence vectors of all (not necessarily perfect) matchings of a graphG. We consider here the problem of computing the dimension of the face of this polytope which contains the maximum cardinality matchings ofG and give a good characterization of this quantity, in terms of the cyclomatic number of the graph and families of odd subsets of the nodes which are always nearly perfectly matched by every maximum matching.This is equivalent to finding a maximum number of linearly independent representative vectors of maximum matchings ofG; the size of such a set is called thematching rank ofG. We also give in the last section a way of computing that rank independently of those parameters.Note that this gives us a good lower bound on the number of those matchings.     

A note on 1-factors in certain regular multigraphs

Claude Berge has given sufficient conditions under which each edge of a regular multigraph belongs to some 1-factor. His proof-technique actually yields the same conclusion under less restrictive conditions. Here we point out that this stronger version of Berge's theorem follows easily from a theorem on doubly-stochastic matrices proved previously by the author.     

On the relationship between the genus and the cardinality of the maximum matchings of a graph

Lower bounds on the cardinality of the maximum matchings of graphs are established in terms of a linear polynomial of p, p⁽¹⁾, p⁽²⁾ and γ whose coefficients are functions of κ, where p is the number of the vertices of a graph, p⁽ⁱ⁾ the number of the vertices of degree i (i = 1,2), γ the genus and κ the connectivity.     

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664ⁿ) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.