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 with at least vertices is said to satisfy the property if contains a perfect matching and for any two sets of independent edges and with and with , there is a perfect matching in such that and . In particular, if is , we say that is -extendable. One of the authors has proved that every -tough graph of even order at least is -extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for -extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee . |
| |
Keywords: | Toughness Binding number Matching extension Restricted matching extension |
本文献已被 ScienceDirect 等数据库收录! |
|