連結グラフの誘導部分グラフとn-拡張可能性について

关于连通图的导出子图和n-可扩展性

• 批准号: 06740178
• 负责人: 西村 強
• 金额: $ 0.58万
• 依托单位: Shibaura Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06740178/
• 关键词: 1-因子; 誘導部分グラフ; 拡張可能; 再帰的; 連結性

1-因子をもつグラフGがn-拡張可能であるとは、G内にn本の独立辺を任意に指定するとき、これらを含む1-因子に拡張できるときのことをいう.グラフ内に1-因子が存在するための十分条件は19世紀からかなり多数の研究がなされて今日に至っている.その中の古典的な定理に次のようなものがある:位数2pの連結グラフG内の位数2q(p>q>1)の任意の連結誘導部かグラフが1-因子をもつならば、グラフGも1-因子をもつ.これは1974年にSUMNERによって証明されたものであり、グラフの誘導部分グラフによる再帰的条件による定理となっている.この定理をもとに、1993年にNISHIMURAは、n-拡張可能性について類似の定理:Gを位数2p(p【greater than or equal】3)の連結グラフ,q,nを1【less than or equal】n<q<pをみたす整数とする.ある整数qが存在して、Gの位数2qの任意の連結誘導部分グラフがn-拡張可能であれば、このときG自身もn-拡張可能である.を導き、組合せ系学術誌Ars Conbinatoria(CANADA)に発表された.この定理では、位数2qの誘導部分グラフに連結性を仮定し、Gからこの部分グラフを残すように除かれる位数2(p-q)の部分グラフについては、その連結性には条件が入れられていないことがわかる.ここでの研究では、逆に連結グラフGから除いてしまう部分グラフに連結性を仮定することによって新しい結果を作ることを目的としGを位数2pの連結グラフとし、a,nをp-a≧n+1をみたす正整数とする.あるaが存在して、位数2aの任意の連結部分グラフAに対して、GIAがn-拡張可能ならば、Gもn-拡張可能である.この定理の証明においてGIAは連結でなければならないことが要求されるので、1993年に得た定理よりも再帰的条件として調査するGの部分グラフの数量はアルゴリズム的に減っている結果となっている.この定理を証明する論文はEXTENDABLE GRAPHS and INDUCED SUBGRAPHSのタイトルで1994年のSUT Journal of Mathematics誌VOL.30.P129-135に発表された.

1-The factor G is n-expansion possible, and the factor G is n-expansion independent. The existence of 1-factors in the 19th century has been studied for the most part until today. In the classical theorem, the number of digits 2 p of the link G is the number of digits 2 q (p> q> 1) of the arbitrary link induction part. This is the proof of Sumner's theorem in 1974. NISHIMURA (1993) Similar theorem: G digit number 2 p (p [greater than or equal] 3) links q, n 1 [less than or equal] n <q <p integer. The integer q exists, the number of digits of G is 2 q, and any link induction part of G is n-expansion possible, G itself is n-expansion possible. Ars Conbinatoria (CANADA) is an academic journal. This theorem is based on the following conditions: 1) the number of bits 2 q of the induction part of the chain is determined; 2) the number of bits 2 (p-q) of the induction part of the chain is determined; 3) the number of bits 2 (p-q) of the induction part of the chain is determined; 4) the number of bits 2 (p-q) of the induction part of the chain is determined; 5) the number of bits 2 q of the induction part of the chain is determined; 6) the number of bits 2 q of the induction part of the chain is determined; 7) the number of bits 2 (p-q) of the induction part of the chain is determined; 8) the number of bits 2 q of the induction part of the chain is determined; 9) the number of bits 2 (p-q) of the induction part of the chain is determined; 8) the number of bits 2 (p-q) of the induction part of the chain is determined; 9) the number of bits 2 (p-q) of the induction part of the chain is determined; 8) the number of bits 2 (p-q) of the induction The study is based on the following: 1. The study is based on the following: 1. The study is based on the study of the relationship between the two groups: 1. A exists, bits 2a are linked arbitrarily, A corresponds, GIA is n-open possible, G is n-open possible. The proof of this theorem is based on the GIA's link to the theorem in 1993. The theorem is based on the condition that the theorem is re-examined. The number of parts of the theorem is based on the result of the investigation. The proof of this theorem is presented in the paper EXTENDABLE GRAPHS and INDUCED SUBGRAPHS published in SUT Journal of Mathematics Vol.30.P129 - 135 in 1994.

项目成果

TSUYOSHI NISHIMURA: "EXTENDABLE GRAPHS AND INDUCED SUBGRAPHS" SUT Journal of Mathematics. 30. 129-135 (1994)

TSUYOSHI NISHIMURA：“可扩展图和归纳子图”SUT 数学杂志。