Description
An interesting graph parameter \mu(G) is investigated
which is connected to the
Manickam-Miklós-Singhi Conjecture; \mu(G) is the minimum number of edges
covering all perfect 2-matchings.
As determining \mu(G) is NP-hard even for very special cases, we study the
minimum and the maximum of this parameter over realizations of a given degree
sequence.
For regular degree sequences we determined exactly both the minimum and the
maximum.
Then we show that for any given sequence, the minimum can be calculated in
polynomial time.
Joint work with my students at BSM: Neeraja Kulkarni,
Ian McMeeking and Joshua Mundinger.
In the second (shorter) part we determine the minimum number of matchings
covering all vertices.
Joint work with Dehia Ait Ferhat, András Sebő and Gautier Stauffer.