7K-07
1-factor-criticalのグラフにおける任意の辺を閉路に含む奇数耳分解について
○淺見勇璃,金 鎔煥,片山喜章(名工大)
耳分解問題とは2辺連結グラフG=(V,E)上の辺集合をE=P0∪P1∪…∪Pkである耳と呼ばれる単純経路Pi(0≦i≦k)に分解する問題で,すべてのPiが奇数長であるとき奇数耳分解という.1-factor-criticalとはG=(V,E)の任意の頂点v∈Vに対してV-{v}で誘導される誘導部分グラフが完全マッチングを持つグラフであり,奇数耳分解の有無により判定可能である.本研究では任意の1-factor-criticalグラフ上で任意の辺をP0(閉路)に含む奇数耳分解が可能であることを示す.