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.

Review text

Summary: Answering a question posed by \textit{Y. Caro} et al. [``Graphs isomorphisms under edge-replacements and the family of amoebas, Preprint, \url{arXiv:2007.11769}], we show that for every positive integer \(n\) and every function \(\sigma: E(K_{4n})\to\{-1,1\}\) with \(\sigma(E(K_{4n}))=0\), there is a perfect matching \(M\) in \(K_{4n}\) with \(\sigma(M)=0\). Strengthening the consequence of a result of \textit{Y. Caro} and \textit{R. Yuster} [Graphs Comb. 32, No. 1, 49--63 (2016; Zbl 1331.05098)], we show that for every positive integer \(n\) and every function \(\sigma: E(K_{4n})\to\{-1,1\}\) with \(|\sigma(E(K_{4n}))|<n^2+11n+2,\) there is a perfect matching \(M\) in \(K_{4n}\) with \(|\sigma(M)|\leqslant 2\). 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

(11)

• On the number of group-weighted matchings
• Group weighted matchings in bipartite graphs
• Zero-sum \(K_m\) over \(\mathbb{Z}\) and the story of \(K_4\)
• On zero-sum spanning trees and zero-sum connectivity
• Zero-sum copies of spanning forests in zero-sum complete graphs
• Almost color-balanced perfect matchings in color-balanced complete graphs
• Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation
• Unbalanced spanning subgraphs in edge labeled complete graphs
• The balancing number and generalized balancing number of some graph classes
• On the existence of zero-sum perfect matchings of complete graphs
• A uniform bound on almost colour-balanced perfect matchings in colour-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)