Low weight perfect matchings

DOI10.37236/9994MaRDI QIDQ2223441zbMATH OpenOpenAlexFDO

Authors Stefan Ehard, Elena Mohr, Dieter Rautenbach

Publication date 29 January 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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

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)

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.

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

Cites work

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

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)