ScholarLens Back to search
2010•Discrete Mathematics Algorithms and ApplicationsRequires access

BIPARTITE MATCHING EXTENDABILITY AND TOUGHNESS

Xiumei Wang, Sujing Zhou, Yixun Lin

Open publisher page 2 citations

Abstract

Let G be a simple graph containing a perfect matching. G is said to be bipartite matching extendable (BM-extendable) if every matching M which is a perfect matching of an induced bipartite subgraph extends to a perfect matching of G. In this paper, we study some relations between toughness and BM-extendability of a graph, including some sufficient or necessary conditions about toughness for a graph to be BM-extendable, and a sufficient condition for a BM-extendable graph to be 1-tough.

About this research paper

What this paper is about

Let G be a simple graph containing a perfect matching. G is said to be bipartite matching extendable (BM-extendable) if every matching M which is a perfect matching of an induced bipartite subgraph extends to a perfect matching of G. In this paper, we study some relations between toughness and BM-extendability of a graph, including some sufficient or necessary conditions about toughness for a graph to be BM-extendable, and a sufficient condition for a BM-extendable graph to be 1-tough.

Why it matters

OpenAlex reports 2 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Let G be a simple graph containing a perfect matching. G is said to be bipartite matching extendable (BM-extendable) if every matching M which is a perfect matching of an induced bipartite subgraph extends to a perfect matching of G. In this paper, we study some relations between toughness and BM-extendability of a graph, including some sufficient or necessary conditions about toughness for a graph to be BM-extendable, and a sufficient condition for a BM-extendable graph to be 1-tough.

Key concepts: Bipartite graph, Factor-critical graph, Matching (statistics), Combinatorics, 3-dimensional matching, Mathematics, Toughness, Graph

Related papers

Related paper 1Related paper 2
Back to paper searchBrowse research topicsOriginal source
BIPARTITE MATCHING EXTENDABILITY AND TOUGHNESS — Research Paper | ScholarLens