連結グラフの独立辺集合の拡張可能性と回避可能性について

连通图中独立边集的可扩展性及避免

• 批准号: 08740159
• 负责人: 西村 強
• 金额: $ 0.64万
• 依托单位: Shibaura Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08740159/
• 关键词: 1-因子; n-拡張可能; n-回避可能

1-因子をもつグラフGがn-拡張可能であるとは,G内の任意のn本の独立辺を指定するとき,これらを含む1-因子が存在するときのことをいう.ここでの研究では,Gにm本の独立辺を指定するとき,これらの辺集合を含むことのない1-因子が存在するための条件を捜すことにあったが,この研究における研究費の申請時と同じ時期にPorteousとAldredによって,「P【greater than or equal】2(m+n+1),M,Nを互いに素なGのマッチング,|M|=m,|N|=n,とするときGがM⊆PかつN∩P=φとなる1-因子Pをもつとき,Gは性質E(m,n)をもつ」ということについての研究が行われており,E(m,n)の諸々の命題が明らかにされてしまった.しかしながら,彼らの研究では行われていない次のような結果を導くことができたのでこれを報告することにする.1-因子をもつグラフGがn-回避可能であるとは,高々サイズがnであるような任意のマッチングMに対し,G-Mが1-因子をもつときのこと定理1.n>0,Gがn-拡張可能であれば,Gはn-回避可能である.この結果の証明の本質的な部分はPlummerの定理を用いることであった.さらに,グラフGの位数2kの任意の連結部分がグラフSに対し,Sがn-回避可能であるときを(k,n)-回避可能,G-Sがn-回避可能のときのことを[k,n]-回避可能とよぶことにするとき,次のような結果を得る.定理2.Gが連結かつ(k,n)-回避可能ならば,Gは(k+1,n)-回避可能定理3.Gが連結かつ(k,n)-回避可能ならば,Gは[k-1,n]-回避可能どちらの結果も証明の基本的な部分は,TnHeの1-因子定理を用いて構造の考察から証明をしている.

1-Factor 1-factor-1-factor This is an example of how to do this. G