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

DOI10.1016/J.DISC.2011.08.026zbMATH Open1238.05213OpenAlexW2146296585MaRDI QIDQ658043FDOQ658043

Authors: Artur Khojabaghyan, Vahan V. Mkrtchyan 

Publication date: 11 January 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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)leq2l(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)$.

Full work available at URL: https://arxiv.org/abs/0901.0121

Recommendations

• On complexity of special maximum matchings constructing
• Characterizations of maximum matching graphs of certain types
• On matchings in graphs
• Matchability and \(k\)-maximal matchings
• Maximum matchings in a regular graph of specified connectivity and bounded order

zbMATH Keywords

matchingbipartite graphmaximum matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Matching theory
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parallel concepts in graph theory
• The path partition problem and related problems in bipartite graphs
• On complexity of special maximum matchings constructing

Cited In (3)

• Tutte sets in graphs. II: The complexity of finding maximum Tutte sets
• Title not available (Why is that?)
• On complexity of special maximum matchings constructing

This page was built for publication: On upper bounds for parameters related to the construction of special maximum matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658043)