Two recursive theorems on n-extendibility

✍ Scribed by Tsuyoshi Nishimura; Akira Saito

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 255 KB
• Volume: 162
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00298-b

✦ Synopsis

We give two recursive theorems on n-extendible graphs. A graph G is said to be (k,n)extendible if every connected induced subgraph of G of order 2k is n-extendible. It is said to be [k, hi-extendible if G -V(H) is n-extendible for every connected induced subgraph H of G of order 2k. In this note we prove that every (k, n)-extendible graph is (k + l, n + 1)-extendible and that every [k, n]-extendible graph is [k -1, n]-extendible. Both are natural generalizations of recent results by Nishimura ([1, 2]).

For a nonnegative integer n, a graph G is said to be n-extendible if G has n independent edges, and every set of n independent edges extends to a perfect matching. In particular, G is 0-extendible if and only if G has a perfect matching.

In [4] Sumner has given a sufficient condition for a graph to have a perfect matching in terms of a perfect matching of its subgraphs.