Two recursive theorems on n-extendibility

AbstractWe 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, n]-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 + 1, 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])