2010Shinjang dashösi ilmiy jurniliRequires access

Degree sum and connectivity conditions for bipartite matching extendable graphs

Biao Zhao

Open publisher page 0 citations

Abstract

A graph G is said to be bipartite matching extendable if every matching M which is a perfect matching of an induced bipartite subgraph can be extended to a perfect matching of G.For a graph G,let δ k (G) be the minimum degree sum of an independent set of k vertices,let κ(G) be the connectivity of a graph G.In this paper,we prove that if G is a graph of order 2n with κ(G) ≥ 2 (n/2)+1 and δ 3 (G) ≥ 3 (3n/2)-2,then G is bipartite matching extendable graph.We also show that the bound for the conditions are almost the best possible.

About this research paper

What this paper is about

A graph G is said to be bipartite matching extendable if every matching M which is a perfect matching of an induced bipartite subgraph can be extended to a perfect matching of G.For a graph G,let δ k (G) be the minimum degree sum of an independent set of k vertices,let κ(G) be the connectivity of a graph G.In this paper,we prove that if G is a graph of order 2n with κ(G) ≥ 2 (n/2)+1 and δ 3 (G) ≥ 3 (3n/2)-2,then G is bipartite matching extendable graph.We also show that the bound for the conditions are almost the best possible.

Why it matters

A significance statement is not available in the OpenAlex record.

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

A graph G is said to be bipartite matching extendable if every matching M which is a perfect matching of an induced bipartite subgraph can be extended to a perfect matching of G.For a graph G,let δ k (G) be the minimum degree sum of an independent set of k vertices,let κ(G) be the connectivity of a graph G.In this paper,we prove that if G is a graph of order 2n with κ(G) ≥ 2 (n/2)+1 and δ 3 (G) ≥ 3 (3n/2)-2,then G is bipartite matching extendable graph.We also show that the bound for the conditions are almost the best possible.

Key concepts: Bipartite graph, Combinatorics, Factor-critical graph, Mathematics, Matching (statistics), Edge-transitive graph, Graph factorization, Degree (music)

Related papers

Back to paper searchBrowse research topicsOriginal source
Degree sum and connectivity conditions for bipartite matching extendable graphs — Research Paper | ScholarLens