Discrete Mathematics & Theoretical Computer Science |

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: arXiv.org:1807.11159

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

This page has been seen 941 times.

This article's PDF has been downloaded 382 times.