首页 | 本学科首页   官方微博 | 高级检索  
     


Toughness,binding number and restricted matching extension in a graph
Authors:Michael D. Plummer  Akira Saito
Affiliation:1. Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA;2. Department of Information Science, Nihon University, Sakurajosui 3–25–40, Setagaya-Ku, Tokyo 156–8550, Japan
Abstract: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 MN=?, there is a perfect matching F in G such that M?F and NF=?. 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).
Keywords:Toughness  Binding number  Matching extension  Restricted matching extension
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号