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

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-因子をもつグラフ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-因子定理を用いて構造の考察から証明をしている.