Toughness, binding number and restricted matching extension in a graph

被引：12
作者：
Plummer, Michael D. [1 ]
Saito, Akira [2 ]
机构：
[1] Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA
[2] Nihon Univ, Dept Informat Sci, Setagaya Ku, Sakurajosui 3-25-40, Tokyo 1568550, Japan
来源：
DISCRETE MATHEMATICS | 2017年 / 340卷 / 11期
基金：
日本学术振兴会;
关键词：
Toughness; Binding number; Matching extension; Restricted matching extension;
D O I：
10.1016/j.disc.2016.10.003
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A connected graph G with at least 2m + 2n + 2 vertices is said to satisfy the property E(m, n) if G contains a perfect matching and for any two sets of independent edges M and N with |M| = m and |N| = n with M boolean AND N = empty set, there is a perfect matching F in G such that M subset of F and N boolean AND F = empty set. In particular, if G is E(m, 0), we say that G is m-extendable. One of the authors has proved that every m-tough graph of even order at least 2m + 2 is m-extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for m-extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee E(m, n). (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码：2665 / 2672
页数：8
相关论文
共 24 条
[11]  
Chartrand G., 2011, Graphs and Digraphs
[12]   BINDING NUMBER AND TOUGHNESS FOR MATCHING EXTENSION [J].
CHEN, CP .
DISCRETE MATHEMATICS, 1995, 146 (1-3) :303-306
[13]  
Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6
[14]   COMPUTING THE BINDING NUMBER OF A GRAPH [J].
CUNNINGHAM, WH .
DISCRETE APPLIED MATHEMATICS, 1990, 27 (03) :283-285
[15]   On the restricted matching extension of graphs in surfaces [J].
Li, Qiuli ;
Zhang, Heping .
APPLIED MATHEMATICS LETTERS, 2012, 25 (11) :1750-1754
[16]   On the restricted matching extension of graphs on the torus and the Klein bottle [J].
Li, Qiuli ;
Zhang, Heping .
DISCRETE MATHEMATICS, 2012, 312 (16) :2450-2456
[17]  
Liu GZ, 1998, ARS COMBINATORIA, V48, P129
[18]  
Plummer M.D., 1996, SURV GRAPH THEOR SAN, V116, P3
[19]   TOUGHNESS AND MATCHING EXTENSION IN GRAPHS [J].
PLUMMER, MD .
DISCRETE MATHEMATICS, 1988, 72 (1-3) :311-320
[20]   EXTENDING MATCHINGS IN GRAPHS - A SURVEY [J].
PLUMMER, MD .
DISCRETE MATHEMATICS, 1994, 127 (1-3) :277-292
123