独立数と特別な全域木
斎藤研究室 疋田暁大
目次
・全域木とは
・branch vertex、leafとは
・独立集合と独立数とは
・スパイダーとは
・claw-freeとは
・先行研究、研究動機
・結果
・証明
・結果の拡張
・まとめ
・今後の課題
全域木とは
グラフのすべての頂点を含む部分木。
leafとは
次数1の頂点
branch vertexとは
次数3以上の頂点
独立集合と独立数とは
スパイダーとは
branch vertexが1つの木。
claw-freeとは
どの4点もclawを誘導しないグラフ
claw-freeの例 claw-freeでない例
先行研究
定理(Ｍａｔｓｕｄａ，Ｏｚｅｋｉ，Ｙａｍａｓｈｉｔａ ２０１４）
連結な claw-freeグラフ Ｇ がα（Ｇ）≦２ｋ＋２ を満 たせば branch vertex がｋ個以下の全域木がＧに存在 する。
ｋ＝１とすると…
先行研究
定理(Ｍａｔｓｕｄａ，Ｏｚｅｋｉ，Ｙａｍａｓｈｉｔａ ２０１４）
連結な claw-freeグラフ Ｇ がα（Ｇ）≦４ を満たせば branch vertex が１個以下の全域木がＧに存在する。
ｋ＝１とすると…
スパイダー
先行研究、研究動機
claw-freeを使わずα(G)≦4のときどんな全域木でも 証明できるか。
系
連結な claw-free グラフ Ｇ がα（Ｇ）≦４ を満たせ ば Ｇには全域スパイダーが存在する。
結果
α(G)≦4の時、次のグラフを除いて全域スパイダーが 存在する。
証明
Gにはスパイダーが存在しないと仮定する。
Ｇから全域木Tを次のようにとる。
(1)できるだけbranch vertexが少ないもの (2)(1)の中でleafが最も少ないもの
以上のことを使い証明していく。
lｅａｆは独立である。
Leaf同士は独立でないと仮定する。
すると、ある２つのleaf同士の間に辺が存在する。
leafが独立であるため、α(G)≦4より、branch vertexの 個数が1つと2つの時しか存在しない。
それぞれ|B(T)|=1,|B(T)|=2とする。
(i) B(T)=１のとき
となりスパイダーが存在してしまうため仮定に矛盾す る。
(ii) |B(T)|=2のとき
次のグラフしか存在しない
P1,P2,P3,P4の辺上には頂点がいくつも存在している かもしれない。
ここで(3)の条件を加える。
(3) (1)(2)の中でbranch vertex同士の距離が一番短い ものをとる。
(1)できるだけbranch vertexが少ないもの (2)(1)の中でleafが最も少ないもの
X1とX2の間に頂点が存在すると仮定する。
(3)のbranch vertex同士の距離が最も短いものを取る ことに矛盾する。
(1)できるだけbranch vertexが少ないもの (2)(1)の中でleafが最も少ないもの
(3) (1)(2)の中でbranch vertex同士の距離が 一番短いものをとる。
(2)α(G)≦4よりどれかの5つの独立点の間に辺が存 在する。
X1とY3のとき
スパイダーが存在するので矛盾
スパイダーが存在しないためX1とY1が辺で繋がって いるとしてよい。
この時、X1がY1の親になっている場合eは存在しない。
以下X1がY1の親でないとする。
(3)Z1はP1におけるX1の隣接点とする。
Z1,Y1,Y2,Y3,Y4の5つの頂点をとる。α(G)≦4と主張1 よりZ1とY1,Y2,Y3,Y4のいずれかの間に辺が存在する。
Z1がY1と繋がっている場合
スパイダーは存在しないため、Z1とY1に辺が存在する。
(4)Z1の2つの隣接点のうちX1でない方をZ2とする。
α(G)≦4と主張1よりY1≠Z2ならばZ2とY1,Y2,Y3,Y4の いずれかに辺が存在する。
Z2がY1と繋がっている場合
スパイダーは存在しないため、Z2とY1に辺が存在する。
(4)を繰り返すと...
ZnがY1と繋がっている場合
スパイダーは存在しないため、ZnとY1に辺が存在する。
以上より、Y1は、X1とP1-Y1のすべての頂点と繋がっ ていることが分かる。
(5) Z1からZnはそれぞれ葉になることができる。
・Z1がとき
Znが葉になる時
以上より次のグラフが取れる。
次にP2,P3,P4について同じように考えると
P1
P2 P3
P4
X1とK2の任意の頂点に辺がないとする X1とK3がつながっているとき
スパイダーが存在するので矛盾。
K1
K3 K2
K4
X1 X2
完全グラフ
完全グラフ 完全グラフ
完全グラフ
X1とK1がつながっているとき K1の任意の頂点につながる。
どの頂点も葉になれるので...
X2とK3の任意の頂点に辺がないとする X2とK2がつながっているとき
スパイダーが存在するので矛盾。
K1
K3 K2
K4
X1 X2
完全グラフ
完全グラフ 完全グラフ
完全グラフ
X2とK4がつながっているとき K4の任意の頂点につながる。
K1
K3 K2
K4
X1 X2
完全グラフ 完全グラフ
完全グラフ 完全グラフ
以上より、この1種類のグラフを除いてグラフGにはス パイダーが存在する。
まとめ
claw-freeの条件を抜いて全域スパイダーが存在する ことを証明できた。
α(G)≦4の時、次のグラフを除いて全域スパイダーが 存在する。
今後の課題
最大独立集合α(G)≧5の時、同じように全域スパイ ダーが存在するかどうか。
