On upper bounds for parameters related to construction of special maximum matchings

Abstract

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)\le 2l(G),$ and $L(G)\le (3/2)l(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)=(3/2)l(G)$.

11 pages, no figures

References in corpus (1)

• On complexity of special maximum matchings constructing

Cited by in corpus (1)

• Three results towards the approximation of special maximum matchings in graphs