Low weight perfect matchings

DOI10.37236/9994zbMATH Open1456.05070arXiv2010.15418OpenAlexW3113933922MaRDI QIDQ2223441FDOQ2223441

Authors: Stefan Ehard, Elena Mohr, Dieter Rautenbach 

Publication date: 29 January 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Answering a question posed by Caro, Hansberg, Lauri, and Zarb, we show that for every positive integer $n$ and every function $sigmacolonE(K_{4n})o-1,1$ with $sigmaleft(E(K_{4n})ight)=0$, there is a perfect matching $M$ in $K_{4n}$ with $sigma(M)=0$. Strengthening a result of Caro and Yuster, we show that for every positive integer $n$ and every function $sigmacolonE(K_{4n})o-1,1$ with $left|sigmaleft(E(K_{4n})ight)ight|<n^2+11n+2,$ there is a perfect matching $M$ in $K_{4n}$ with $|sigma(M)|leq2$. Both these results are best possible.

Full work available at URL: https://arxiv.org/abs/2010.15418

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Computing Minimum-Weight Perfect Matchings
• Fast and Simple Algorithms for Weighted Perfect Matching
• Perfect matchings and applications
• A weighted perfect matching with constraints on weights of its parts
• Weighted matching with pair restrictions
• Maintaining perfect matchings at low cost
• Minimum-weight perfect matching for nonintrinsic distances on the line
• Weighted connected matchings
• Perfect matching and polymatroids
• Weighted restricted 2-matching

zbMATH Keywords

spanning graphs

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Zero-sum problems -- a survey
• On zero-sum and almost zero-sum subgraphs over \(\mathbb Z\)

Cited In (8)

• On the existence of zero-sum perfect matchings of complete graphs
• Zero-sum copies of spanning forests in zero-sum complete graphs
• Zero-sum \(K_m\) over \(\mathbb{Z}\) and the story of \(K_4\)
• Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation
• On zero-sum spanning trees and zero-sum connectivity
• The balancing number and generalized balancing number of some graph classes
• Unbalanced spanning subgraphs in edge labeled complete graphs
• Almost color-balanced perfect matchings in color-balanced complete graphs

This page was built for publication: Low weight perfect matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223441)