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

    Consultation statistics

    This page has been seen 1062 times.
    This article's PDF has been downloaded 470 times.