For a graph G let L(G) and l(G) denote the size of the largest and smallest maximum matching of a graph obtained from G by removing a maximum matching of G. We show that L(G)@?2l(G), and L(G)@?32l(G) provided that G contains a perfect matching. We also characterize the class of graphs for which L(G)=2l(G). Our characterization implies the existence of a polynomial algorithm for testing the property L(G)=2l(G). Finally we show that it is NP-complete to test whether a graph G containing a perfect matching satisfies L(G)=32l(G).
['Artur Khojabaghyan', 'Vahan V. Mkrtchyan']
On upper bounds for parameters related to the construction of special maximum matchings