ティーツェのグラフ

ティーツェのグラフ
ティーツェのグラフ
	ティーツェグラフ
頂点	12
エッジ	18
半径	3
直径	3
胴回り	3
自己同型	12 ( D 6 )
彩度数	3
色指数	4
プロパティ	キュービック・; スナーク
	グラフとパラメータの表

数学のグラフ理論の分野において、ティーツェのグラフは12の頂点と18の辺を持つ無向立方グラフである。このグラフは、1910年にメビウスの帯を互いに接する6つの領域（帯の境界に沿って3つ、中心線に沿って3つ）に分割できること、したがってメビウスの帯に埋め込まれるグラフには6 色が必要になる可能性があることを示したハインリヒ・フランツ・フリードリヒ・ティーツェにちなんで名付けられた。^[1]ティーツェの細分領域の境界セグメント（メビウスの帯自体の境界に沿ったセグメントを含む）は、ティーツェのグラフの埋め込みを形成する。

ピーターセングラフとの関係

ティーツェグラフは、ピーターセングラフの頂点の1つを三角形に置き換えることで形成できます。 ^[2]^[3] ティーツェグラフと同様に、ピーターセングラフは6つの相互に接する領域の境界を形成しますが、メビウスの帯上ではなく射影平面上にあります。射影平面のこの分割から1つの頂点を囲む穴を切り取ると、囲まれた頂点は穴の周りの領域境界の三角形に置き換えられ、前述のティーツェグラフの構築が得られます。

ハミルトン性

ティーツェグラフとピーターセングラフはどちらも最大非ハミルトングラフです。つまり、ハミルトン閉路はありませんが、隣接していない任意の2つの頂点はハミルトンパスで接続できます。^[2]ティーツェグラフとピーターセングラフは、12個以下の頂点を持つ唯一の2頂点接続立方非ハミルトングラフです。^[4]

ピーターセングラフとは異なり、ティーツェグラフは非ハミルトングラフではありません。3 つの三角形の頂点のうち 1 つを削除すると、非ハミルトングラフのまま小さいグラフが形成されます。

エッジカラーリングと完璧なマッチング

Tietze グラフの辺の色付けには4 つの色が必要です。つまり、彩度指数は 4 です。同様に、Tietze グラフの辺は 4 つのマッチングに分割できますが、それより少なくすることはできません。

ティーツェのグラフはスナークの定義の一部に一致している。すなわち、3辺に色を付けられず、ブリッジのない立方グラフである。しかし、ほとんどの著者はスナークを3サイクルのないグラフに限定しているため、ティーツェのグラフは一般にスナークとは見なされていない。しかし、 1975年にR.アイザックスが導入したフラワースナークの無限族の一部であるグラフJ _3と同型である^。[5]

ピーターセングラフとは異なり、ティーツェグラフは4つの完全マッチングで覆われる。この性質は、グラフが4つの完全マッチングで覆われるかどうかをテストすることがNP完全であることを証明する上で重要な役割を果たします。^[6]

追加のプロパティ

ティーツェのグラフは彩色数 3、彩色指数 4、内周3、直径3です。独立数は 5 です。自己同型群の位数は 12 で、正六角形の対称群 (回転と反射の両方を含む) である二面体群 D 6 と同型です。この群には頂点_上にサイズ 3 の軌道が 2 つとサイズ 6 の軌道が 1 つあるため、このグラフは頂点推移的ではありません。

ギャラリー

ティーツェグラフの彩色数は3 です。
Tietze グラフの色指数は4 です。
Tietze グラフは交差数が 2 で、 1 平面グラフです。
Tietze グラフの 3 次元埋め込み。

参照

デューラーグラフとフランクリングラフ、他の2つの12頂点立方グラフ

注記

^ Tietze、Heinrich (1910)、「Einige Bemerkungen zum 問題 des Kartenfärbens auf einseitigen Flächen」 [片面の地図の色付けの問題に関するいくつかのコメント] (PDF)、DMV Annual Report、19 : 155–159
^ ab Clark, L.; Entringer, R. (1983)、「最小最大非ハミルトングラフ」、Periodica Mathematica Hungarica、14 (1): 57–68、doi :10.1007/BF02023582、S2CID 122218690
^ ワイスタイン、エリック W.「ティーツェのグラフ」。マスワールド。
^ Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007)、「ほぼハミルトン立方グラフ」(PDF)、International Journal of Computer Science and Network Security、7 (1): 83–86
^ アイザックス、R. (1975)、「テイト色付け可能でない非自明な三価グラフの無限族」、アメリカ数学月刊誌、82 (3)、アメリカ数学協会: 221–239、doi :10.2307/2319844、JSTOR 2319844。
^ Esperet, L.; Mazzuoccolo, G. (2014)、「4 つの完全マッチングでエッジセットをカバーできない立方ブリッジレスグラフについて」、Journal of Graph Theory、77 (2): 144–157、arXiv : 1301.6926、doi :10.1002/jgt.21778、MR 3246172、S2CID 15284123。

[1] Tietze、Heinrich (1910)、「Einige Bemerkungen zum 問題 des Kartenfärbens auf einseitigen Flächen」 [片面の地図の色付けの問題に関するいくつかのコメント] (PDF)、DMV Annual Report、19 : 155–159

[CE-2] Clark, L.; Entringer, R. (1983)、「最小最大非ハミルトングラフ」、Periodica Mathematica Hungarica、14 (1): 57–68、doi :10.1007/BF02023582、S2CID 122218690

[3] ワイスタイン、エリック W.「ティーツェのグラフ」。マスワールド。

[4] Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007)、「ほぼハミルトン立方グラフ」(PDF)、International Journal of Computer Science and Network Security、7 (1): 83–86

[5] アイザックス、R. (1975)、「テイト色付け可能でない非自明な三価グラフの無限族」、アメリカ数学月刊誌、82 (3)、アメリカ数学協会: 221–239、doi :10.2307/2319844、JSTOR 2319844。

[6] Esperet, L.; Mazzuoccolo, G. (2014)、「4 つの完全マッチングでエッジセットをカバーできない立方ブリッジレスグラフについて」、Journal of Graph Theory、77 (2): 144–157、arXiv : 1301.6926、doi :10.1002/jgt.21778、MR 3246172、S2CID 15284123。