Let G be a bridgeless cubic graph. A well-known conjecture of Berge and Fulkerson can be stated as follows: there exist five perfect matchings of G such that each edge of G is contained in at least one of them. Here, we prove that in each bridgeless cubic graph there exist five perfect matchings covering a portion of the edges at least equal to 215 231 . By a generalization of this result, we decrease the best known upper bound, expressed in terms of the size of the graph, for the number of perfect matchings needed to cover the edge-set of G.

Covering a cubic graph with perfect matchings / Mazzuoccolo, Giuseppe. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 313:20(2013), pp. 2292-2296. [10.1016/j.disc.2013.06.006]

Covering a cubic graph with perfect matchings

Mazzuoccolo, Giuseppe
2013

Abstract

Let G be a bridgeless cubic graph. A well-known conjecture of Berge and Fulkerson can be stated as follows: there exist five perfect matchings of G such that each edge of G is contained in at least one of them. Here, we prove that in each bridgeless cubic graph there exist five perfect matchings covering a portion of the edges at least equal to 215 231 . By a generalization of this result, we decrease the best known upper bound, expressed in terms of the size of the graph, for the number of perfect matchings needed to cover the edge-set of G.
2013
313
20
2292
2296
Covering a cubic graph with perfect matchings / Mazzuoccolo, Giuseppe. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 313:20(2013), pp. 2292-2296. [10.1016/j.disc.2013.06.006]
Mazzuoccolo, Giuseppe
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/1310844
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact