Given two positive integers l and m, with l≤m, an [l,m]-covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l≤;|M|≤m for every M. An [l,m]-covering M of G is an excessive [l,m]-factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive [l,m]-factorization of G (or ∞, if G does not admit an excessive [l,m]-factorization) is a graph parameter called the excessive [l,m]-index of G and denoted by χ[l,m]′(G). In this paper we study such parameter. Our main result is a general formula for the excessive [l,m]-index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes χ[l,m]′(G) for any fixed constants l and m and outputs an excessive [l,m]-factorization of G, whenever the latter exists.

Excessive [l,m]-factorizations

Mazzuoccolo, Giuseppe
2015-01-01

Abstract

Given two positive integers l and m, with l≤m, an [l,m]-covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l≤;|M|≤m for every M. An [l,m]-covering M of G is an excessive [l,m]-factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive [l,m]-factorization of G (or ∞, if G does not admit an excessive [l,m]-factorization) is a graph parameter called the excessive [l,m]-index of G and denoted by χ[l,m]′(G). In this paper we study such parameter. Our main result is a general formula for the excessive [l,m]-index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes χ[l,m]′(G) for any fixed constants l and m and outputs an excessive [l,m]-factorization of G, whenever the latter exists.
2-s2.0-84926610349
File in questo prodotto:
File Dimensione Formato  
cariolaro_mazzuoccolo_revised_4.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Accesso ristretto
Dimensione 325.51 kB
Formato Adobe PDF
325.51 kB Adobe PDF Visualizza/Apri

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: https://hdl.handle.net/11562/933057
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact