pith. sign in

arxiv: 0901.0121 · v3 · pith:JXD2BIORnew · submitted 2008-12-31 · 💻 cs.DM · math.CO

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

classification 💻 cs.DM math.CO
keywords matchinggraphmaximumperfectalgorithmboundscharacterizationcharacterize
0
0 comments X
read the original 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)\leq 2l(G),$ and $L(G)\leq (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)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.