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

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.
Perfect matching
Maximal matching
Cubic graph
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

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