サブハミルトングラフ

グラフ理論とグラフ描画において、サブハミルトングラフは平面ハミルトングラフの部分グラフです。^{[1] [2]}

定義

グラフGがサブハミルトングラフであるとは、Gが同じ頂点集合上の別のグラフaug( G )の部分グラフであり、aug( G )が平面グラフであり、ハミルトン閉路を含む場合を言う。これが成り立つためには、G自体が平面グラフでなければならず、さらに、平面性を保ちながらGに辺を追加して、各頂点をちょうど1回通過する閉路を作成できる必要がある。グラフaug( G )はGのハミルトン拡張と呼ばれる。^[2]

Gがハミルトン平面グラフの部分グラフである場合に、G をサブハミルトングラフと定義することと等価である。ただし、このより大きなグラフが同じ頂点集合を持つ必要はない。つまり、この代替定義では、 Gに頂点と辺の両方を追加してハミルトン閉路を作成することが可能であるべきである。しかし、グラフを頂点と辺の追加によってハミルトングラフにできる場合、辺のみの追加によってもハミルトングラフにすることができるため、この追加の自由度は定義を変更するものではない。^[3]

サブハミルトングラフにおいて、サブハミルトン閉路とは、頂点の巡回列であり、その列内の連続する頂点のペア間に辺を追加することでグラフの平面性が保たれる。グラフがサブハミルトングラフであるためには、サブハミルトン閉路が存在する必要がある。^[4]

歴史と応用

サブハミルトングラフのクラス（ただし、この名前は使われていません）は、BernhartとKainen（1979）によって導入されました。彼らは、これらがまさに2ページの本の埋め込みを持つグラフであることを証明しました。^[5]サブハミルトングラフとハミルトン拡張は、グラフ描画において、普遍点集合へのグラフの埋め込み、複数グラフの同時埋め込み、階層化グラフ描画などの問題にも適用されています。^[2]

関連するグラフクラス

平面グラフのいくつかのクラスは必然的にハミルトングラフであり、したがって部分ハミルトングラフでもあります。これには、4連結平面グラフ、ハミルトン閉路に関するトゥッテの定理^[6]、およびハリングラフ^[7]が含まれます

最大次数が4以下のすべての平面グラフはサブハミルトングラフである^[4]。同様に、分離三角形のないすべての平面グラフもサブハミルトングラフである^[8] 。 任意の平面グラフの辺を長さ2のパスに分割した場合、結果として得られる分割グラフは常にサブハミルトングラフである^{[2] 。}

参考文献

1. Heath, Lenwood S. (1987)、「小さな本への外平面グラフの埋め込み」、SIAM Journal on Algebraic and Discrete Methods、8 (2): 198– 218、doi :10.1137/0608018、MR  0881181。
2. Di Giacomo, Emilio; Liotta, Giuseppe (2010)、「ハミルトン増加問題とグラフ描画への応用」、WALCOM: アルゴリズムと計算、第4回国際ワークショップ、WALCOM 2010、バングラデシュ、ダッカ、2010年2月10～12日、議事録、コンピュータサイエンス講義ノート、第5942巻、ベルリン：Springer、pp.  35～ 46、doi :10.1007/978-3-642-11440-3_4、ISBN 978-3-642-11439-7、MR  2749626。
3. 、2003年の技術レポート「グラフの埋め込みとホイットニーの定理」の中で、ポール・カイネンは、サブハミルトングラフを平面ハミルトングラフのサブグラフとして定義し、拡張の頂点集合に制限を設けていませんが、「サブハミルトングラフの定義では、拡張には新しい辺の追加のみが必要であると要求できる」と書いています
4. ベコス、マイケル A.;グローネマン、マーティン。 Raftopoulou、Chrysanthi N. (2014)、「2 ページのブックの 4 平面グラフの埋め込み」、STACS、arXiv : 1401.0684、Bibcode :2014arXiv1401.0684B。
5. バーンハート、フランク・R.;カイネン、ポール・C. (1979)、「グラフの本の厚さ」、Journal of Combinatorial Theory、シリーズB、27 (3): 320– 331、doi : 10.1016/0095-8956(79)90021-2。
6. 西関隆雄、千葉則重 (2008)、「第10章 ハミルトン閉路」、平面グラフ：理論とアルゴリズム、ドーバー数学書籍、クーリエ・ドーバー出版、pp.  171– 184、ISBN 9780486466712。
7. コルヌエジョルス, G. ; ナデフ, D. ;プーリーブランク, WR (1983)、「ハリングラフと巡回セールスマン問題」、数理計画、26 (3): 287– 294、doi :10.1007/BF02591867、S2CID  26278382。
8. カイネン、ポール・C.；オーバーベイ、シャノン（2007）、「ホイットニーの定理の拡張」、応用数学レター、20（7）：835–837、arXiv：2110.00820、doi：10.1016/j.aml.2006.08.019、MR  2314718。