## Hongliang Lu ; Qinglin Yu - Binding Number, Toughness and General Matching Extendability in Graphs

dmtcs:4723 - Discrete Mathematics & Theoretical Computer Science, January 17, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-1
Binding Number, Toughness and General Matching Extendability in GraphsArticle

Authors: Hongliang Lu ; Qinglin Yu

A connected graph $G$ with at least $2m + 2n + 2$ vertices which contains a perfect matching is $E(m, n)$-{\it extendable}, if for any two sets of disjoint independent edges $M$ and $N$ with $|M| = m$ and $|N|= n$, there is a perfect matching $F$ in $G$ such that $M\subseteq F$ and $N\cap F=\emptyset$. Similarly, a connected graph with at least $n+2k+2$ vertices is called $(n,k)$-{\it extendable} if for any vertex set $S$ of size $n$ and any matching $M$ of size $k$ of $G-S$, $G-S-V(M)$ contains a perfect matching. Let $\varepsilon$ be a small positive constant, $b(G)$ and $t(G)$ be the binding number and toughness of a graph $G$. The two main theorems of this paper are: for every graph $G$ with sufficiently large order, 1) if $b(G)\geq 4/3+\varepsilon$, then $G$ is $E(m,n)$-extendable and also $(n,k)$-extendable; 2) if $t(G)\geq 1+\varepsilon$ and $G$ has a high connectivity, then $G$ is $E(m,n)$-extendable and also $(n,k)$-extendable. It is worth to point out that the binding number and toughness conditions for the existence of the general matching extension properties are almost same as that for the existence of perfect matchings.

Volume: Vol. 21 no. 3
Section: Graph Theory
Published on: January 17, 2019
Accepted on: December 13, 2018
Submitted on: July 31, 2018
Keywords: Mathematics - Combinatorics
Funding:
Source : OpenAIRE Graph
• Funder: Natural Sciences and Engineering Research Council of Canada