Strongly maximal matchings in infinite graphs

Authors Ron Aharoni, Eli Berger, Agelos Georgakopoulos, Philipp Sprüssel

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0911.4010, https://eudml.org/doc/117277, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r136.html

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

infinite graph matching strongly weight maximal matching weighted edges

Mathematics Subject Classification ID

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

Abstract: Given an assignment of weights w to the edges of a graph G, a matching M in G is called strongly w-maximal if for any matching N the sum of weights of the edges in NM is at most the sum of weights of the edges in MN. We prove that if w assumes only finitely many values all of which are rational then G has a strongly w-maximal matching.

Review text

Summary: Given an assignment of weights \(w\) to the edges of an infinite graph \(G\), a matching \(M\) in \(G\) is called strongly \(w\)-maximal if for any matching \(N\) there holds \[ \sum\left\{w(e) \mid e \in N \setminus M\right\} \leq \sum\left\{w(e) \mid e \in M \setminus N\right\}. \] We prove that if \(w\) assumes only finitely many values all of which are rational then \(G\) has a strongly \(w\)-maximal matching. This result is best possible in the sense that if we allow irrational values or infinitely many values then there need not be a strongly \(w\)-maximal matching.

Recommendations

Cited in

(5)

This page was built for publication: Strongly maximal matchings in infinite graphs

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