Back to Search
Start Over
Excessive [formula omitted]-factorizations.
- Source :
-
Discrete Mathematics . Nov2015, Vol. 338 Issue 11, p1917-1927. 11p. - Publication Year :
- 2015
-
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 ∈ 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 338
- Issue :
- 11
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 103425189
- Full Text :
- https://doi.org/10.1016/j.disc.2015.04.030