2014-01-20 Hamilton Cycles (Graph Theory, Chapter 10) Siffocoemt conditions 頂点数3以上,すべての頂点の次数が n/2 位上ならハミルトニアン 頂点数3以上,α(G)≦κ(G) ならハミルトニアン α:最大独立集合,κ:連結性 頂点数3以上連結,任意の induced path uvw で d(u)+d(w)≧|N(u)∪N(v)∪N(w)| ならハミルトニアン Hamilton cycles and degree sequences 4-connected な平面グラフはハミルトニアン 次数列 (a_1, a_2, ..., a_n) はハミルトニアン ⇔ (a_i ≦ i ⇒ a_{n-i} ≧ n-i) ここでいう次数列とは,小さいものからソートして考える 次数列がハミルトニアンとは,全 i で次数 d_i≧a_i になればグラフが必ずハミルトニアンであるということ Square of a graph 2-connected なら, G^2 はハミルトニアン