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

dmtcs:4723 - Discrete Mathematics & Theoretical Computer Science, January 17, 2019, Vol. 21 no. 3
Binding Number, Toughness and General Matching Extendability in Graphs

Authors: Lu, Hongliang and Yu, Qinglin

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.


Source : oai:arXiv.org:1807.11159
Volume: Vol. 21 no. 3
Section: Graph Theory
Published on: January 17, 2019
Submitted on: July 31, 2018
Keywords: Mathematics - Combinatorics


Share