کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423295 | 1342323 | 2015 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Excessive [l,m]-factorizations Excessive [l,m]-factorizations](/preview/png/6423295.png)
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.
Journal: Discrete Mathematics - Volume 338, Issue 11, 6 November 2015, Pages 1917-1927