タフネスと閉曲面上のグラフのハミルトン性
小関 健太(国立情報学研究所)∗

1. はじめに
本稿では私の研究テーマの一つである，“閉曲面上のグラフのハミルトン性” について述べる．特に，下の言葉はこの研究の根幹にあり，またモチベーションでもある．この言葉の意味と根拠を伝えること目標に，本稿を展開したいと思う．
閉曲面上のグラフの連結度とハミルトン性の関係はタフネス型の条件に従うと考えられる．

2. 準備
2.1. ハミルトン性
グラフのすべての頂点を通る閉路をハミルトン閉路と呼び，すべての頂点を通る道をハミルトン道と呼ぶ．与えられたグラフのハミルトン性に関する問題は，巡回セール
スマン問題との関わりがあるなど重要なものとなっている．特にグラフを平面グラフ 1など閉曲面上のものに限ると，この問題は四色定理とも関わりを持つため，多くの研究が行われている．実際に，Tait [62] は 1880 年に「任意の 3-連結 3-正則平面グラフ 23
がハミルトン閉路を持つならば四色定理は正しい」ということを示している．後にこの命題の仮定は誤っていることが示されたため，（例えば Tutte [68] など）Tait の結果
は四色定理の証明とはならなかったが，閉曲面上のグラフのハミルトン性に関しての研究が以後盛んに行われることになった．
例えば，1931 年に Whitney [72] が「平面の任意の 4-連結な三角形分割はハミルト
ン閉路を持つ」ことを示し，その結果を Tutte [69] は一般の 4-連結平面グラフへと拡張しているなど，肯定的な結果がいくつも示されている．本稿の研究もこの流れに沿うものである．
ここで，グラフ G が「任意の 2 頂点 x, y に対し x と y を結ぶハミルトン道が存在する」という性質を満たすとき，G はハミルトン連結であるという 4 ．ここで，PH , PHP ,PHC でハミルトン性に関連した次の性質をそれぞれ表すことにする．

PH : ハミルトン閉路を持つ
PHP : ハミルトン道を持つ
PHC : ハミルトン連結である
JST, ERATO, 河原林巨大グラフプロジェクト
2010 Mathematics Subject Classification: 05C10, 05C38
キーワード：ハミルトン閉路, タフネス, 平面グラフ, 閉曲面上のグラフ，連結度，タフネス，全域木∗〒 101-8430 東京都千代田区一ツ橋 2-1-2 国立情報学研究所
e-mail: ozeki@nii.ac.jp
web: http://comb.math.keio.ac.jp/ozeki/
1
平面に辺の交差なく埋め込まれたグラフを平面グラフと呼ぶ．以下，本稿で閉曲面上のグラフというときは，その閉曲面に辺の交差なく埋め込まれたグラフのことを指す．
2
任意の k 点未満の頂点集合を取り除いても連結であるとき，グラフは k-連結と呼ばれる．
3
すべての頂点にちょうど 3 本の辺が接続しているグラフを 3-正則 と呼ぶ.
4
なお，グラフが「ハミルトン連結ならばハミルトン閉路を持ち」「ハミルトン閉路を持つならばハミルトン道を持つ」ことが容易に示される．

2.2. タフネス
次の形の条件はグラフのタフネスと呼ばれるものである 5 ．ここで，グラフ G の連結
成分数を ω(G) と書く．

(∗)

ω(G−S) ≥ 2 となる任意の頂点集合 S に対し 6 ，ω(G−S) ≤ a|S|+bが成り立つ．

タフネスは，1973 年に Chvátal [16] によって定義されたものである．特に，Chvátal( )[16] の「ある定数 t が存在して，(∗) を (a, b) = 1t , 0 で満たす任意のグラフはハミル
トン閉路を持つ」という予想は，現在でも重要な未解決な問題である 7 ．グラフのハミ
ルトン性に関して，次のタフネス型の必要条件が自明に成り立つ.
命題 1 グラフ G がハミルトン閉路を持つならば，(∗) が (a, b) = (1, 0) で成り立つ.
本稿ではこの形の必要条件を持つグラフの性質と閉曲面上のグラフの関係について考察を行う．ここで，各性質 P に対し，次の値 aP と bP を定義する．ただし，min は
辞書式順序での最小を取る．また，そのような aP と bP が存在しない性質 P は本稿では考えないこととする．
{}(aP , bP ) = min (a, b) : 性質 P を満たす任意のグラフ G で (∗) が成り立つ .
例えば，命題 1 より，(aPH , bPH ) ≤ (1, 0) となる．これと，完全二部グラフ Km,m を考えることによって，(aPH , bPH ) = (1, 0) がわかる．同様にして，(aPHP , bPHP ) = (1, 1) か
つ (aPHC , bPHC ) = (1, −1) であることも示される．
また，タフネスと関係の深い性質として，「最大次数の制限された全域木が存在する」というものが挙げられる．ここで，グラフ G の全域木で最大次数が k 以下のもの
を G の k-木と呼ぶ．また，Pk-tree で「k-木を持つ」という性質を表すことにすると，(aPk-tree , bPk-tree ) = (k − 1, 1) となることが知られている 8 ．
ここで，k-木の性質をさらに拡張し，超過数を定義する．グラフ G の全域木 T と
k ≥ 2 なる自然数 k に対し，T の k からの超過数を te(T, k) と書き，

te(T, k) =∑{}max degT (v) − k, 0v∈V (T )と定義する 9 ．te(T, k) = 0 であるとき，T は k-木と一致する．また k = 2 のとき，
te(T, 2) ≤ t である木 T は「葉の数が t + 2 以下である木」と同値である．ここで，P(k,t)-tree で「k からの超過数が t 以下の全域木を持つ」という性質を表すことにすると，(aP(k,t)-tree , bP(k,t)-tree ) = (k − 1, t + 1) となることが知られている．
5

正確にはタフネス型の条件と呼ぶ．通常，単にタフネスというと b = 0 のときのみを考える．タフネ
スの詳細は，Bauer, Broersma と Schmeichel によるサーベイ [6] を参照．
6
すなわち，任意のカットセット S に対し，7
この予想が未解決であるように，一般にタフネスからハミルトン閉路を見つけることは難しい．
Bauer, Broersma と Veldman [7] は，そのような定数 t が存在するとしたら t ≥ 94 となることを示している．
8
k-木に関して Win [73] はタフネス型の十分条件を与えている．全域木のサーベイ [53] も参照.
9degT (v) で頂点 v の T での次数を表す．

2.3. 閉曲面
本稿では平面 (球面)，射影平面，トーラス，クラインボトルをはじめとした閉曲面を扱う．各閉曲面 F2 のオイラー標数を χ(F2 ) で表す．オイラーの定理より，オイラー標数
χ の閉曲面上に埋め込まれた任意のグラフ G に対し，|V (G)| − |E(G)| + |F (G)| ≥ χが成り立つ．ただし，F (G) でグラフ G の面全体の集合を表す．平面 (球面)，射影平面，トーラス，クラインボトルのオイラー標数 χ の値は，それぞれ 2, 1, 0, 0 である．
また，閉曲面上に埋め込まれたグラフについて，下の二つの命題はよく知られたものである．
命題 2 (Schmeichel and Bloom [61]) k ≥ 3 とし，
χ の閉曲面(G をオイラー標数)
2−2χ
上の k-連結グラフとする．このとき，(∗) が (a, b) =で成り立つ．
,
k−2 k−2
命題 3 k = 3, 4, 5 とし，χ ≤ 2 とする．このとき，オイラー標数 χ の任意の閉曲面 F2に対し，F2 上のある k-連結グラフ G とその頂点部分集合 S ⊂ V (G) で，ω(G − S) ≥ 2
かつ，
2
−2χ
ω(G − S) =
|S| +
k−2
k−2
が成り立つ 10 ．
また，平面でない閉曲面 F2 上に埋め込まれたグラフ G に対し，G の representativity を rep(G) と書き，以下のように定義する．
{}
211
rep(G) = min |G ∩ γ| : γ は F 上の非可縮な閉曲線.

representativity が (閉曲面のオイラー標数に比べて) 十分に高いグラフは 局所平面的であると呼ばれ，平面グラフに似た様々な良い性質を持つことが知られている．例えば，命題 2 と同様にして，以下が証明される．
2
命題 4 k ≥ 3，χ ≤ 1 とし，a0 > k−2
かつ b0 ≥ −ka0 + 2 とする．このとき，ある12定数 r が存在して ，オイラー標数 χ の閉曲面上の任意の k-連結グラフ G に対し，rep(G) ≥ r ならば，(∗) が (a, b) = (a0 , b0 ) で成り立つ．

2.4. 研究の目的
本稿では，3 以上の整数 k と PH , PHP , PHC など，グラフのハミルトン性に関する性
質 P に対し，ある閉曲面 F2 上の，任意の k-連結グラフが性質 P を満たすという命題を考えていく 13 ．もちろん，命題 3 を考えると，「性質 P のタフネス型の必要条件を満たしていない F2 上の k-連結グラフが存在する」という理由から，“反例”
そのような G は F2 の三角形分割となるものに限ったとしても無限個存在する.
すなわち，2-胞体領域の境界とならない閉曲線 γ とグラフ G が交わる回数の最小値である.
12
なお，Archdeacon, Hartsfield と Little [1] の構成したグラフより，命題 4 の定数 r は χ に無関係には存在できないことがわかる．
13
この内容は Ellingham によるサーベイ [21] も参照．
1011

が容易に見つかるような閉曲面 F2 と性質 P の組がある．しかしながら，上記の形の命題の，タフネス以外の理由による “反例” は現在までほとんど見つかっていない 14 ．
本稿では，上記の形のさまざまな肯定的な結果および予想を紹介する．それらを根拠として，「上記の形の命題は，タフネス型の必要条件さえ満せば肯定的に成り立つ」ということを主張したいと思う．最初に述べたように，この意味で閉曲面上のグラフの連結度と性質 P の関係は “タフネス” に従うと考えられるのである．

3. 4-連結性と aP = 1 となる性質 P
この章では閉曲面上の 4-連結グラフに注目する．ここで命題 2 より，オイラー標数 χの閉曲面上の 4-連結グラフ G に対し，(∗) が (a, b) = (1, −χ) で成り立つことがわかる．したがって，PH , PHP や PHC など，aP = 1 であるいくつかの性質 P については
タフネス型の必要条件を満たすことが命題 2 より導かれる．一方で，bP の値によっては，性質 P のタフネス型の必要条件を満たさない閉曲面上の 4-連結グラフが存在する
ことも，命題 3 より示せる．
例えば，トーラスのオイラー標数 χ の値は 0 であるので，bPHC = −1 < −χ よりトーラス上の 4-連結グラフでハミルトン連結でないものが存在することがわかる．以上の理由より，この章では aP = 1 かつ bP ≥ −χ であるような，オイラー標数 χ の閉曲面と性質 P のペアを考える．
表 1: 閉曲面上の 4-連結グラフのハミルトン性.

PHP (bPHP = 1)
平面
χ=2
射影平面
χ=1
トーラス
χ=0
クラインボトル
χ=0N3
χ = −1その他
χ ≤ −2

Thomas, Yu& Zang [65]河原林 & 小関 [43]PH (bPH = 0)?

PHC (bPHC = −1)

Tutte [69]15

Thomassen [66]17

Thomas & Yu [63]16

河原林 & 小関 [38]18

Grünbaum [30]Nash-Williams [48]?

?

3.1. ハミルトン閉路，ハミルトン道，ハミルトン連結
本節では aP = 1 となる性質 P のうち，PH , PHP , PHC の 3 性質に注目する．上で述べたように, 閉曲面のオイラー標数の値によってはそれぞれの性質を満たさないグラフが存在してしまう．そういったグラフが存在するとき，表 1 の対応する領域に “×” を記

14

本稿の最後に述べる「最大次数の制限された 2-連結な全域部分グラフが存在する」という性質が，現在知られている唯一の例外である．ただし，その例もタフネスに関係した理由で “反例” が存在する．
15
Tutte 自身による，少し簡単な証明 [70] も知られている．
16
Thomas と Yu が示す以前は，Grünbaum の予想 [30] として知られていた．
17
千葉と西関 [15] は，Thomassen の証明のミスを指摘し，同時にその修正も発表している．
18
我々が示す以前は，Dean の予想 [18] として知られていたものである．

している．また，表 1 の “○” の領域は，その領域に対応する命題が成り立つことを意味している．表の “？” は，その命題が成り立つかどうか，まだわかっていない．
表 1 で示しているように，4-連結グラフのハミルトン性に関して，Tutte [69] やThomassen [66] の結果など，いくつかの肯定的な結果が知られているが，次の大きな予想が未解決で残っている．
予想 5 (Grünbaum [30], Nash-Williams [48]) トーラス上の任意の 4-連結グラフ
はハミルトン閉路を持つ．
予想 5 の周辺では，表 1 にあるようないくつもの肯定的な命題が示されているが，その一方で予想 5 はいまだ解決されていない．その中で，藤沢氏 (慶應義塾大学), 中
本氏 (横浜国立大学) との共同研究で得られた以下の結果は，タフネスと関連した結果である．
定理 6 (藤沢, 中本, 小関 [25, 47]) トーラスの任意の 4-連結グラフ G において，ある頂点集合 S で ω(G − S) ≥ 2 かつω(G − S) = |S|が成り立つならば 19 ，G はハミルトン閉路を持つ．
したがって，命題 2 より，予想 5 は「トーラス上の 4-連結グラフで，(∗) が (a, b) =(1, −1) で成り立つ」グラフのみを対象にすればよい．なお，Tutte [69], Thomassen[66], Thomas & Yu [63] らの平面・射影平面上のグラフにおける結果では，すべて，「平
面・射影平面上の任意の 4-連結グラフでは，(∗) が (a, b) = (1, −1) で成り立つ」ことを利用している 20 ．したがって，Tutte [69] らが平面・射影平面上のグラフで成功した手法をトーラス上のグラフへと適用することで予想 5 が解決できる可能性がある．
また，私は，河原林氏 (国立情報学研究所) との最近の共同研究で予想 5 は三角形分割では正しいことを示している．
定理 7 (河原林, 小関 [40]) トーラスの任意の 4-連結な三角形分割はハミルトン閉路を持つ．

3.2. 平面グラフと (aP , bP ) = (1, −2) となる性質 P
ここで，グラフを 4-連結平面グラフに限定すると，命題 2 より bP = −2 となる性質
P に対してもタフネス型の必要条件を満たすため，ハミルトン連結より強い性質を持つことが期待される．実際に，Plummer [54] は「任意の 4-連結平面グラフは，任意の2 頂点を取り除いてもハミルトン閉路を持つ」ことを予想し，Thomas と Yu [63] はこの予想を肯定的に解決している 21 ．また，Thomassen [66] のハミルトン連結の結果の拡張として，「任意の 4-連結平面グラフは，任意の 2 頂点 x, y と任意の辺 e に対し，xと y を結び e を通るハミルトン道を持つ」こと，および「任意の 4-連結平面グラフ Gは，任意の頂点を取り除いてもハミルトン連結である 22 」ことが，Sanders [58] の定理
19すなわち，命題 2 の等号を満たすような頂点集合 S を持つグラフ G では
すなわち，ハミルトン閉路を持つことを，bP ≤ −1 となるより強い性質 P を持つことで示している．
21
この話題は，Malkevitch [44] による，「四角形を持つ任意の 4-連結平面グラフ G は，3 ≤ l ≤ |G| である任意の l に対し，長さ l の閉路を持つ」という予想と関連している．[14] も参照．
22
この性質は 1-ハミルトン連結 と呼ばれる.
20

の系として示される．([57] も参照.) なお，これらの結果にある三つの性質をそれぞれ，
P2H , P2eHC′ , P1HC と書くと，(aP2H , bP2H ) = (aP2eHC′ , bP2eHC′ ) = (aP1HC , bP1HC ) = (1, −2)であることが，命題 1 と同様にして証明できる．
本節では，性質 P1HC と P2eHC′ よりさらに強い 2 辺-ハミルトン連結 という性質に()
注目する 23 ．グラフ G が，任意の e1 , e2 ∈ V (G)に対し 24 ，G + {e1 , e2 } が辺 e1 , e2 を2共に通るハミルトン閉路を持つとき，G は 2 辺-ハミルトン連結であるという．P2eHC
を「2 辺-ハミルトン連結である」という性質として定義すると，この性質 P2eHC も(aP2eHC , bP2eHC ) = (1, −2) を満たしている．私は Vràna 氏 (University of West Bohemia)との共同研究で，Sanders の定理の系を拡張し以下の結果を示している 25 ．
定理 8 (小関, Vràna [52]) 任意の 4-連結平面グラフは 2 辺-ハミルトン連結である．
また，1 頂点を共有する 2 つの点素な閉路からなるグラフを figure-eight グラフと呼び，共有されている頂点を中心と呼ぶ．Rosenfeld [56] は，「任意の 4-連結平面グラフ
は，任意の頂点を中心とする figure-eight グラフを全域部分グラフとして持つ」ことを示している．この性質 P もタフネスに関係あり，実際に (aP , bP ) = (1, 0) を満たしている．したがって，上の 2 辺-ハミルトニアンと同様に，もっと強い性質が期待できる．

3.3. 負のオイラー標数を持つ閉曲面と bP > 0 となる性質 P
表 1 にあるように，χ(F2 ) ≤ −2 である任意の閉曲面 F2 に対し，F2 上の 4-連結グラ
フでハミルトン道を持たないものが存在する．これは，命題 3 と bPHP = 1 < −χ という関係からわかる．したがって本節では PHC より弱い性質として，性質 P(2,t)-tree に注目する 26 ．なお，(aP(2,t)-tree , bP(2,t)-tree ) = (1, t + 1) である．この性質に対しても，命題 2 と 3 を考えることによって以下の命題が成り立つと予想される．
問題 9 (小関 [50]) オイラー標数 χ < 0 の閉曲面上の任意の 4-連結グラフは 2 からの超過数が −χ − 1 以下の全域木を持つ．
また，命題 4 より，閉曲面上の局所平面的な 4-連結グラフでは，(∗) が a = 2 でも成り立つ．これに注目したのが，Ellingham, Gao [22] と Yu [71] らであり，彼らは「閉曲面上の局所平面的な任意の 4-連結グラフは 3-木を持つ」ことを示している．Mohar(P. 181 [45] を参照) は，局所平面的な 4-連結グラフは上の二つの両方の性質を同時に満たす全域木を持つことを予想しており，Böhme, Mohar と Thomassen [9] はある種の部分的解決を与えている．私は，最近，河原林氏との共同研究で予想 10 の別の部分的解決を行った．
予想 10 (Mohar [45]) オイラー標数 χ < 0 の任意の閉曲面 F2 に対し，ある定数r = r(F2 ) が存在して，F2 上の任意の 4-連結グラフ G は rep(G) ≥ r ならば，3-木であり，かつ 2 からの超過数が O(−χ) である全域木を持つ．
2 辺-ハミルトン連結が，性質 P2H よりも真に強い性質かどうかは不明だが，性質 P2H は満たすが 2
辺-ハミルトン連結ではないグラフが存在する．よって，少なくとも性質 P2H より弱い性質ではない．
24
e1 , e2 は G の辺であっても良いし，そうでなくとも良い．e2 を G の辺に限るとき，2 辺-ハミルトン連結という性質は性質 P2eHC′ と一致する．また，e1 と e2 が端点を共有しているときに限ると性質
P1HC と一致する．
25
正確には，Sanders のオリジナルの結果を拡張し，その系として定理 8 を示している．
26
前に述べたように，この性質は「葉の数が t + 2 以下の全域木を持つ」という性質と同値である.

23

定理 11 (河原林, 小関 [41]) 予想 10 は，グラフを閉曲面の三角形分割に限定すると
正しい．

4. 5-連結性と aP ≥ 23 となる性質 P
本章では，閉曲面上の 5-連結グラフについて考察を行う．4-連結グラフのハミルトン性において，表 1 の “?” で示されている未解決な問題や “×” で示されている成り立
たない命題が存在するが，“5-連結” という強い仮定を置くことによって様々な肯定的な結果が得られている．例えば，Thomas と Yu [64] は，予想 5 は 5-連結グラフに限定すれば正しいことを示している．表 2 にあるように，その他にもいくつかの肯定的な結果が知られている 27 ．
表 2: 閉曲面上の 5-連結グラフのハミルトン性.

PHP
平面
χ=2
射影平面
χ=1
トーラス
χ=0
クラインボトル
χ=0
その他 (局所平面的)χ ≤ −1?

PH

PHC

Thomas & Yu [64]河原林 & 小関 [42]河原林 & 小関 [42]河原林 & 小関 [42]? Thomassen [67]?

ここで，一般の閉曲面上の 5-連結グラフへとハミルトン性の拡張を考える．前章で述べたように，この拡張は，命題 3 より “4-連結” という仮定では不可能であるが，“局所平面的” な “5-連結” グラフを考えると，命題 4 よりタフネス型の必要条件を満たすことがわかる．この事実を一つの根拠として，Thomassen は以下の予想を立てている．(P. 182 [45] と [71] も参照.)
予想 12 (Thomassen [67]) オイラー標数 χ < 0 の任意の閉曲面 F2 に対し，ある定
数 r = r(F2 ) が存在して，任意の F2 上の 5-連結グラフ G は rep(G) ≥ r ならば，ハミルトン閉路を持つ．
予想 12 は未解決であるが，Yu [71] は，予想 12 を三角形分割に限定すると正しいことを示している．さらに，河原林 [35] は Yu の結果を拡張し，局所平面的で 5-連結な三角形分割はハミルトン連結であることを示している．
その一方で命題 2 より，閉曲面上の 5-連結グラフは 1 > aP ≥ 32 である性質 P に対してもタフネス型の必要条件を満たしている．したがって，そのような性質 P を考える下の問題は興味深いものだと思われるが，これに関して現在ではほとんど何も知られていない．
27

表 2 にはないが，それ以外にもいくつかの結果が知られている．Barnette [3] と，Brunet と Richter[12] は Thomas と Yu [64] 以前に「トーラスの任意の 5-連結な三角形分割はハミルトン道，ハミル
トン閉路を持つ」ことをそれぞれ示している．また，Brunet, 中本 と 根上 [11] はクラインボトルに関しての同様の命題を証明した.

表 3: 閉曲面上の 3-連結グラフのハミルトン性.

χ=0

Pk-tree
Barnette [2](k = 3) 29
Barnette [4](k = 3)Barnette [4](k = 3)その他 (局所平面的)

Yu [71]

平面
χ=2
射影平面
χ=1
トーラス・クラインχ ≤ −1その他
χ ≤ −1(k = 4) 30

P(2,t)-tree
中本, 小田, 太田 [46](t = |G|−73) 32

中本, 小田, 太田 [46](t = |G|−7
3)

中本, 小田, 太田 [46]((t = |G|−33t = |G|+O(1)3Sanders & Zhao [60]

小関⌉)
[49]
(太田 ⌈&−2χ+831
k=3P(3,t)-tree?

(t = 0)(t = 0))(t = 0)) 33(t = −2χ − 1) 34
河原林, 中本, 太田 [36](t = −2χ − 1)
小関 [50]問題 13 どのような性質 P が，1 > aP ≥ 32 を満たすか？ また，平面 (または閉曲面)上の 5-連結グラフは，その性質 P を持つか？

5. 3-連結性と aP = 2 となる性質 P
いままで見たように，閉曲面上の 4-連結グラフはハミルトン性に関するいくつかの性質を持つ．本章では，3-連結グラフに関しての同様の考察を行う．命題 2 より，オイ
ラー標数 χ の閉曲面上の 3-連結グラフ G に対し，(∗) が (a, b) = (2, −2χ) で成り立
ち，また，命題 3 より，この値は最善となる．したがって本章では，aP(3,t)-tree = 2 である性質 P(3,t)-tree に注目する．また，Pk-tree や P(2,t)-tree に関してもいくつかの結果が示されているため，同時に記す 28 ．
表 3 は，この流れの研究のいままでの結果をまとめたものである．なお，表の “○”は対応する全域木の存在が，k または t に関して最善の値で示されていることを表し，“△” は肯定的な命題はあるものの最善性は不明であることを意味する．

6. 終わりに
本稿では，閉曲面上のグラフの連結度とハミルトン性の関係を，タフネスという側面から調べてきた．第 2.4 章でも述べたように，閉曲面 F2 上のグラフとハミルトンに関わる性質 P との関係は，タフネス型の必要条件を満たさないという理由により否定的な結論が得られているものも多いが，その一方で，必要条件を満たしながら性質 P を持たない，という例はほとんど見つかっていない．実際に，第 3 章〜第 5 章において，必要条件を満たしている閉曲面 F2 上のグラフとハミルトンに関わる性質 P のペアにおいて，さまざまな肯定的な命題が得られることを示してきた．また，肯定的な命題がまだ得られていなくとも，その命題が成り立つと予想されていることも多い．この意味で上記の関係が「タフネス型の条件に従っている」と考えている．

28

ただし，P(2,t)-tree の肯定的な命題に関しては，命題 3 より t は定数にはなれない．表 3 の場合，tはグラフの頂点数に依存している.

本稿では，性質 P として，PH , PHP , PHC や全域木に関するものを扱ってきたが，その周辺にも多くの興味深い性質があり，また閉曲面上のグラフとの関係，タフネスとの関係など多くの研究がなされている．それらを調べることによって，はじめに述べた「タフネス型の条件に従う」性質の全体像がより明確になることを期待している．そのうちのいくつかの性質と参考文献を紹介して，本稿を終わりたいと思う．
閉曲面上のグラフのハミルトン性についてはもっと多くの研究が知られている．例
えば，3-連結な平面の三角形分割 35 における結果 [13, 19, 31, 33] では，タフネス型の必要条件を成立させるような仮定を加えることによって，ハミルトン閉路の存在を保証している．他にも一般の閉曲面上のグラフのハミルトン性についての研究 [20] も知られている．
第 5 章では，閉曲面上の 3-連結グラフについての研究として k-木のみに注目していたが実際にはもっと多くの研究がなされている．特に，グラフの全域閉歩道について
は，k-木との関係を通してタフネスとも関連があるため，本稿の研究とも深く関わっている ([32] 参照) ．例えば，表 3 における性質 Pk-tree についての全ての結果は，[10, 17, 27, 60, 71] において，閉歩道の存在を示したより強いものへと拡張されている 36 ．また，P(3,t)-tree の局所平面的な場合も [36] で閉歩道の結果が示されている．しかしながら，性質 P(2,t)-tree に関しては，まだほとんどわかっていない．この点の研究は今後の課題である．(問題は [46] を，関連する研究は [28, 29, 39] などを参照.)
これに加えて，プリズム-ハミルトニアン という性質も研究されている．これも 3木や全域閉歩道との関連があるため，タフネス型の条件に従う性質の一つであると予想されており [34, 55]，この予想に関連した研究が進んでいる ([8, 34, 51])．
全域木に関する別の性質として，閉曲面上のグラフの最大次数を制限した 2-連結全域部分グラフ (または，最小次数も制限した連結全域部分グラフ) の存在に関する研究も多い ([5, 23, 24, 26, 36, 37, 59])．この性質もタフネスと関わりがあるのだが，タフネス型の必要条件には完全には従わないことがわかっている．ただし，タフネスに関連した条件には影響されており，この点に関しての今後の研究が待たれている．

参考文献[1] D. Archdeacon, N. Hartsfield and C.H.C. Little, Nonhamiltonian triangulations withlarge connectivity and representativity, J. Combin. Theory Ser. B 68 (1996) 45–55.
29「ハミルトン閉路を持つ」という性質が「ハミルトン連結」へと拡張されたように，この結果も「任意の頂点 x に対し，x を葉にするような 3-木が存在する」という結果へと [46] などで拡張されている．タフネス型の必要条件と命題 2 を考慮すると，もっと強い性質が成り立つと予想される．
30
aP4-tree = 3 と命題 4 に注意せよ．また，Yu [71] 以前に Thomassen [67] は向き付け可能な閉曲面の三角形分割の場合で同じ結果を示している.
31
この k の値もタフネスにより最善であるとわかる．これ以前に，Ellingham [21] は少し弱い結果を示している．また，この結果について，Sanders と Zhao [60] は χ ≤ −36 の場合を示し，後に 太田 と
小関 [49] が χ ≤ −1 へと拡張した.
|G|−1132であると予想している．
中本，太田，小田 [46] は，最善の値は t =333
この結果は，中本，太田，小田 [46] の結果と，閉曲面上の局所平面的な 3-連結グラフの既知の性質(例えば [36] など) を組み合わせることによって得られる．
34
bP(3,t)-tree = t + 1 と命題 2 に注意せよ．また，河原林, 中本, 太田 [36] は，実際には，4-木であり，か
つ 3 からの超過数が −2χ⌈− 1 である全域木が存在することを示している．その下の小関[50] の結果⌉
以下の全域木を得ている．
においても，最大次数が −2χ+8335
一般には，タフネス型の必要条件を満たさないため，ハミルトン閉路を持たないことに注意せよ．
36
ただし，局所平面的でない場合で −1 ≥ χ ≥ −45 のときは除く．その場合は未解決である.

[2] D.W. Barnette, Trees in polyhedral graphs, Canad. J. Math 18 (1966) 731–736.
[3] D.W. Barnette, Decomposition theorems for the torus, projective plane and Klein bottle,
Discrete Math. 70 (1988) 1–16.
[4] D.W. Barnette, 3-trees in polyhedral maps, Israel. J. Math 79 (1992) 251–256.
[5] D.W. Barnette, 2-connected spanning subgraphs of planar 3-connected graphs, J. Combin. Theory Ser. B 61 (1994) 210–216.
[6] D. Bauer, H. Broersma and E. Schmeichel, Toughness in graphs – a survey, Graphs
Combin. 22 (2006) 1–35.
[7] D. Bauer, H. Broersma and H.J. Veldman, Not every 2-tough graph is hamiltonian,
Discrete Appl. Math. 99 (2000) 317–321.
[8] D.P. Biebighauser and M.N. Ellingham, Prism-hamiltonicity of triangulations, J. Graph
Theory 57 (2008) 181–197.
[9] T. Böhme, B. Mohar and C. Thomassen, Long cycles in graphs on a fixed surface, J.
Combin. Theory Ser. B 85 (2002) 338–347.
[10] R. Brunet, M.N. Ellingham, Z. Gao, A. Metzlar and R.B. Richter, Spanning planar
subgraphs of graphs on the torus and Klein bottle, J. Combin. Theory Ser. B 65 (1995)
7–22.
[11] R. Brunet, A. Nakamoto and S. Negami, Every 5-connected triangulation of the Kleinbottle is Hamiltonian, Yokohama Math. J. 47 (1999) 239–244.
[12] R. Brunet and R.B. Richter, Hamiltonicity of 5-connected toroidal triangulations,J. Graph Theory 20 (1995) 267–286.
[13] C. Chen, Any maximal planar graph with only one separating triangle is Hamiltonian,
J. Comb. Optim. 7 (2003) 79–86.
[14] G. Chen, G. Fan and X. Yu, Cycles in 4-connected planar graphs, European J. Combin. 25 (2004) 763–780.
[15] N. Chiba and T. Nishizeki, A theorem on paths in planar graphs, J. Graph Theory 10(1986) 449–450.
[16] V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
[17] Q. Cui, A note on circuit graphs, Electronic J. Discrete Math. 17 (2010) # N10.
[18] N. Dean, Lecture at Twenty-First Southeastern Conference on Combinatorics, Graph
Theory and Computing, Boca Raton, Florida, February 1990.
[19] M.B. Dillencourt, Hamiltonian cycles in planar triangulations with no separating triangles, J. Graph Theory 14 (1990) 31–39.
[20] R.A. Duke, On the genus and connectivity of Hamiltonian graphs, Discrete Math. 2(1972) 199–206.
[21] M.N. Ellingham, Spanning paths, cycles and walks for graphs on surfaces, Congr. Numer. 115 (1996) 55–90.
[22] M.N. Ellingham and Z. Gao, Spanning trees in locally planar triangulations, J. Combin.
Theory Ser. B 61 (1994) 178–198.
[23] M.N. Ellingham and K. Kawarabayashi, 2-Connected spanning subgraphs with low maximum degree in locally planar graphs, J. Combin. Theory Ser. B 97 (2007) 401–412.
[24] H. Enomoto, T. Iida and K. Ota, Connected spanning subgraphs of 3-connected planargraphs, J. Combin. Theory Ser. B 68 (1996) 314–323.
[25] J. Fujisawa, A. Nakamoto and K. Ozeki, Hamiltonian cycles in bipartite toroidal graphswith a partite set of degree four vertices, J. Combin. Theory Ser. B 103 (2013) 46–60.
[26] Z. Gao, 2-connected coverings of bounded degree in 3-connected graphs, J. Graph Theory20 (1995) 327–338.
[27] Z. Gao and R.B. Richter, 2-walks in circuit graphs, J. Combin. Theory Ser. B 62 (1994)
259–267.
[28] Z. Gao, R.B. Richter and X. Yu, 2-walks in 3-connected planar graphs, Australas. J. Combin. 11 (1995) 117–122.
[29] Z. Gao, R.B. Richter and X. Yu, Erratum to: 2-walks in 3-connected planar graphs,
Australas. J. Combin. 36 (2006) 315–316.
[30] B. Grünbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc. 76 (1970)
1131–1201.
[31] G. Helden, Each maximal planar graph with exactly two separating triangles is Hamiltonian, Discrete Appl. Math. 155 (2007) 1833–1836.
[32] B. Jackson and N.C. Wormald, k-walks of graphs, Australas. J. Combin. 2 (1990) 135–
146.
[33] B. Jackson and X. Yu, Hamilton cycles in plane triangulations, J. Graph Theory 41(2002) 138–150.
[34] T. Kaiser, Z. Ryjáček, D. Král’, M. Rosenfeld and H.-J. Voss, Hamilton cycles in prisms,
J. Graph Theory 56 (2007) 249–269.
[35] K. Kawarabayashi, A theorem on paths in locally planar triangulations, European J.
Combin. 25 (2004) 781–784.
[36] K. Kawarabayashi, A. Nakamoto and K. Ota, Subgraphs of graphs on surfaces with highrepresentativity, J. Combin. Theory Ser. B 89 (2003) 207–229.
[37] K. Kawarabayashi, A. Nakamoto and K. Ota, 2-connected 7-coverings of 3-connected
graphs on surfaces, J. Graph Theory 43 (2003) 26–36.
[38] K. Kawarabayashi and K. Ozeki, 4-connected projective planar graphs are hamiltonianconnected, Proceedings of ACM-SIAM Symposium on Discrete Algorithms (2013) 378–
395.
[39] K. Kawarabayashi and K. Ozeki, Spanning closed walks and TSP in 3-connected planargraphs, Proceedings of ACM-SIAM Symposium on Discrete Algorithms (2012) 671–681.
[40] K. Kawarabayashi and K. Ozeki, Hamiltonian cycles in 4-connected triangulations on
torus, preprint.
[41] K. Kawarabayashi and K. Ozeki, Spanning 3-trees with few vertices of degree three inlocally planar graphs, preprint.
[42] K. Kawarabayashi and K. Ozeki, 5-connected graphs on the torus or the Klein bottle
are hamiltonian-connected, preprint.
[43] K. Kawarabayashi and K. Ozeki, 4-connected graphs on the Klein bottle have a hamiltonian path, preprint.
[44] J. Malkevitch, Polytopal graphs, in Selected Topics in Graph Theory, vol. 3, Academic
Press, New York, (1988) 169–188.
[45] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Univ. Press, Baltimore, (2001).
[46] A. Nakamoto, Y. Oda and K. Ota, 3-trees with few vertices of degree 3 in circuit graphs,
Discrete Math. 309 (2009) 666–672.
[47] A. Nakamoto, and K. Ozeki, Hamiltonian cycles in bipartite quadrangulations on thetorus, J. Graph Theory 69 (2012) 143–151.
[48] C.St.J.A. Nash-Williams, Unexplored and semi-explored territories in graph theory, in“New directions in the theory of graphs”, Academic Press, New York, (1973) 149–186.
[49] K. Ota and K. Ozeki, Spanning trees in 3-connected K3,t -minor-free graphs, J. Com-bin. Theory Ser. B 102 (2012) 1179–1188.
[50] K. Ozeki, A spanning tree with bounded maximum degrees of graphs on surfaces, SIAM
J. Discrete Math. 27 (2013) 422–435.
[51] K. Ozeki, Prism hamiltonicity of 3-connected plane graphs with minimum degree atleast 4, preprint.
[52] K. Ozeki and P. Vràna, 2-edge-Hamiltonian connectedness of planar graphs, to appear
in Europe J. Combin.
[53] K. Ozeki and T. Yamashita, Spanning trees – a survey, Graphs Combin. 27 (2011) 1–26.
[54] M.D. Plummer, Problem in infinite and finite sets, in “Colloquia Mathematica SocietatisJános Bolyai 10” 1549–1559, North-Holland, Amsterdam (1975).
[55] M. Rosenfeld, On spanning subgraphs of 4-connected planar graphs, Graphs Combin. 25(1989) 279–287.
[56] M. Rosenfeld and D. Barnette, Hamiltonian circuits in certain prisms, Discrete Math. 5(1973) 389–394.
[57] D.P. Sanders, On hamilton cycles in certain planar graphs, J. Graph Theory 21 (1996)
43–50.
[58] D.P. Sanders, On paths in planar graphs, J. Graph Theory 24 (1997) 341–345.
[59] D.P. Sanders and Y. Zhao, On 2-connected spanning subgraphs with low maximum
degree, J. Combin. Theory Ser. B 74 (1998) 64–86.
[60] D.P. Sanders and Y. Zhao, On spanning trees and walks of low maximum degree,
J. Graph Theory 36 (2001) 67–74.
[61] E.F. Schmeichel and G.S. Bloom, Connectivity, genus, and the number of components
in vertex-deleted subgraphs, J. Combin. Theory Ser. B 27 (1979) 198–201.
[62] P.G. Tait, Remarks on the colouring of maps, Proc. Roya; Soc. London 10 (1880) 729.
[63] R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994) 114–132.
[64] R. Thomas and X. Yu, Five-connected toroidal graphs are hamiltonian, J. Combin.
Theory Ser. B 69 (1997) 79–96.
[65] R. Thomas, X. Yu and W. Zang, Hamilton paths in toroidal graphs, J. Combin. Theory
Ser. B 94 (2005) 214–236.
[66] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169–176.
[67] C. Thomassen, Trees in triangulations, J. Combin. Theory Ser. B 60 (1994) 56–62.
[68] W.T. Tutte, On hamiltonian circuits, J. London Math. Soc. 2 (1946) 98–101.
[69] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99–116.
[70] W.T. Tutte, Bridges and Hamiltonian circuits in planar graphs, Aequationes Math. 15(1977) 1–33.
[71] X. Yu, Disjoint paths, planarizing cycles, and spanning walks, Trans. Amer.
Math. Soc. 349 (1997) 1333–1358.
[72] H. Whitney, A theorem on graphs, Ann. of Math. 32 (1931) 378–390.
[73] S. Win, On a connection between the existence of k-trees and the toughness of a graph,
Graphs Combin. 5 (1989) 201–205.