TY - JOUR

T1 - Two recursive theorems on n-extendibility

AU - Nishimura, Tsuyoshi

AU - Saito, Akira

N1 - Funding Information:
The authors thank Professor Hikoe Enomoto and the referees for valuable comments. Especially, one of the referees pointed out that the word "extendable" in the first version of the paper was a misspelling of "extendible". The work of the second author was partly supported by the Grant in Aid for Scientific Research of the Ministry of Education, Science and Culture of Japan under the grant number: YSE(A) 05780266 (1993).

PY - 1996/12/25

Y1 - 1996/12/25

N2 - 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,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]).

AB - 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,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]).

UR - http://www.scopus.com/inward/record.url?scp=0042542467&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0042542467&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(95)00298-B

DO - 10.1016/0012-365X(95)00298-B

M3 - Article

AN - SCOPUS:0042542467

SN - 0012-365X

VL - 162

SP - 319

EP - 323

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -