Two recursive theorems on n-extendibility

Tsuyoshi Nishimura, Akira Saito

Research output: Contribution to journalArticlepeer-review


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

Original languageEnglish
Pages (from-to)319-323
Number of pages5
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 1996 Dec 25

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Two recursive theorems on n-extendibility'. Together they form a unique fingerprint.

Cite this