Let G be a finite graph (without loops and multiple edges) and let w : E(G) -> [0,+infinity) be a weight function on the edge set of G. We consider the ratio between the maximum weight of a perfect matching of G and the maximum weight of a matching of G. The parameter eta(G), introduced by Brazil & al. in Brazil et al. (2016), is defined as the minimum of such a ratio among all nonnegative edge weight assignments of G. In the present paper, we propose a way to compute a lower bound for the parameter eta(G), and we use it to prove that for every rational number q in the interval [0, 1] there exists a graph G such that eta(G) = q. Moreover, we further use the same method, in combination with some new arguments, to establish the value of eta for Prism graphs and Mobius Ladders. Finally, we improve known results for Blanusa Snarks B-1 and B-2 by determining the exact value of eta(B-1) and eta(B-2). (C) 2021 Elsevier B.V. All rights reserved.

On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching / Mazzuoccolo, Giuseppe; Mella, Lorenzo. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 301:(2021), pp. 19-25. [10.1016/j.dam.2021.05.009]

On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching

Giuseppe Mazzuoccolo;Lorenzo Mella
2021

Abstract

Let G be a finite graph (without loops and multiple edges) and let w : E(G) -> [0,+infinity) be a weight function on the edge set of G. We consider the ratio between the maximum weight of a perfect matching of G and the maximum weight of a matching of G. The parameter eta(G), introduced by Brazil & al. in Brazil et al. (2016), is defined as the minimum of such a ratio among all nonnegative edge weight assignments of G. In the present paper, we propose a way to compute a lower bound for the parameter eta(G), and we use it to prove that for every rational number q in the interval [0, 1] there exists a graph G such that eta(G) = q. Moreover, we further use the same method, in combination with some new arguments, to establish the value of eta for Prism graphs and Mobius Ladders. Finally, we improve known results for Blanusa Snarks B-1 and B-2 by determining the exact value of eta(B-1) and eta(B-2). (C) 2021 Elsevier B.V. All rights reserved.
2021
301
19
25
On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching / Mazzuoccolo, Giuseppe; Mella, Lorenzo. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 301:(2021), pp. 19-25. [10.1016/j.dam.2021.05.009]
Mazzuoccolo, Giuseppe; Mella, Lorenzo
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1310837
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact