Degree sum and connectivity conditions for bipartite matching extendable graphs
Biao Zhao
Abstract
Biao Zhao
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.
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
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)