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.     

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.     

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.     

Circular flow numbers of regular multigraphs

The circular flow number F_c(G) of a graph G = (V, E) is the minimum r ϵ ℚ such that G admits a flow ϕ with 1 ≤ ϕ (e) ≤ r − 1, for each e ϵ E. We determine the circular flow number of some regular multigraphs. In particular, we characterize the bipartite (2t+1)‐regular graphs (t ≥ 1). Our results imply that there are gaps for possible circular flow numbers for (2t+1)‐regular graphs, e.g., there is no cubic graph G with 3 < F_c(G) < 4. We further show that there are snarks with circular flow number arbitrarily close to 4, answering a question of X. Zhu. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 24–34, 2001     

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.     

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$.     

最大匹配的路变换图

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

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.     

Random perfect matchings in regular graphs

We prove that in all regular robust expanders $G$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.     

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

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.