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

DOI10.1016/J.DISC.2011.08.026MaRDI QIDQ658043zbMATH OpenOpenAlexFDO

Authors Artur Khojabaghyan, Vahan V. Mkrtchyan

Publication date 11 January 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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

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

Cites work

• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Matching theory
• On complexity of special maximum matchings constructing
• Parallel concepts in graph theory
• The NP-Completeness of Edge-Coloring
• The path partition problem and related problems in bipartite graphs

Cited in

(3)

• Tutte sets in graphs. II: The complexity of finding maximum Tutte sets
• scientific article; zbMATH DE number 7057487 (Why is no real title available?)
• 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)