花の皮肉

数学のグラフ理論の分野において、フラワースナークは1975年にルーファス・アイザックスによって導入された無限のスナーク族を形成する。 ^[1]

スナークとして、フラワースナークは連結された、ブリッジのない立方グラフで、彩度指数は4です。フラワースナークは非平面で非ハミルトンです。フラワースナークJ5_とJ7_は、本の厚さが3で、キュー番号が2です。 ^[2]

工事

フラワースナーク J _{n は}、次の手順で構築できます。

4 つの頂点に星型グラフのn 個のコピーを作成します。各星型の中心頂点を A _i、外側の頂点を B _i、 C _i、 D _iとします。これにより、4 n個の頂点と 3 n 個の辺 ( 1 ≤ i ≤ nの場合、A _i – B _i、A _i – C _i、A _i – D _i ) を持つ切断されたグラフが生成されます。
nサイクル (B ₁ ... B _n )を構築します。これにより、n 個のエッジが追加されます。
最後に 2 nサイクル (C ₁ ... C _n D ₁ ... D _n ) を構築します。これにより2n 個のエッジが追加されます。

構成上、フラワースナーク J _{n は}4 n頂点と 6 n辺を持つ立方グラフです。必要な特性を持つためには、n は奇数でなければなりません。

フラワースナークという名前は、20頂点30辺のフラワースナークであるJ ₅に使われることがある。 ^[3]これは20頂点の6つのスナークのうちの1つである（OEISの配列A130315）。フラワースナークJ _5は低ハミルトンである。^[4]

J _3はピーターセングラフの単純な変形で、頂点の1つを三角形に置き換えたものである。このグラフはティーツェグラフとしても知られている。^[5]単純なケースを避けるために、スナークは一般的に内周が5以上になるように制限されている。この制限により、J _{3 は}スナークではない。

^ Isaacs, R. (1975). 「Tait 色付け可能でない非自明な 3 価グラフの無限族」. Amer. Math. Monthly . 82 : 221–239. doi :10.1080/00029890.1975.11993805. JSTOR 2319844.
^ Wolz, Jessica; SAT による線形レイアウトのエンジニアリング。修士論文、テュービンゲン大学、2018 年
^ Weisstein, Eric W.「Flower Snark」。MathWorld。
^ Weisstein, Eric W.「Hypohamiltonian Graph」。MathWorld。
^ Clark, L.; Entringer, R. (1983)、「最小最大非ハミルトングラフ」、Periodica Mathematica Hungarica、14 (1): 57–68、doi :10.1007/BF02023582。