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 -