奇妙なグラフ

奇妙なグラフ
${\displaystyle O_{3}=KG(5,2)}$ピーターセングラフは
頂点	${\displaystyle {\tbinom {2n-1}{n-1}}}$
エッジ	${\displaystyle n{\tbinom {2n-1}{n-1}}/2}$
直径	${\displaystyle n-1}$[1] [2]
胴回り	3対5、6対6、それ以外[3]${\displaystyle O_{2}}$ ${\displaystyle O_{3}}$
プロパティ	距離推移
表記	の上
グラフとパラメータの表

数学のグラフ理論の分野において、奇グラフは特定の集合システムから定義される対称グラフの族であり、ピーターセングラフを含み、ピーターセングラフを一般化します。

奇グラフは奇内周が大きく、つまり、奇数長の長いサイクルは含まれるが、短いサイクルは含まれない。しかし、その名前はこの特性から来ているのではなく、グラフの各辺に「外れ値」、つまり辺で接続された 2 つの集合に参加しない要素があるという事実から来ている。

奇グラフは、-元集合の-元部分集合ごとに1つの頂点を持つ。2つの頂点が辺で接続されるのは、対応する部分集合が互いに素である場合に限る。^[2]つまり、はクネザーグラフである。 ${\displaystyle O_{n}}$${\displaystyle (n-1)}$${\displaystyle (2n-1)}$${\displaystyle O_{n}}$ ${\displaystyle KG(2n-1,n-1)}$

${\displaystyle O_{2}}$は三角形であり、 はよく知られているピーターセングラフです。 ${\displaystyle O_{3}}$

一般化奇グラフは、あるに対して直径と奇数の内周を持つ距離正則グラフとして定義されます。^[4] これらには、奇グラフと折り畳み立方体グラフが含まれます。 ${\displaystyle n-1}$${\displaystyle 2n-1}$${\displaystyle n}$

ピーターセングラフは1898年から知られていましたが、奇グラフとして定義されたのは、同じく奇グラフを研究したコワレフスキー（1917）の研究に遡ります。^{[2] [5]奇グラフは、}化学グラフ理論、炭酸イオンの移動のモデル化へ の応用について研究されてきました。^{[6] [7]}並列コンピューティングにおけるネットワークトポロジーとしても提案されています。^[8]${\displaystyle O_{4}}$

これらのグラフの表記法は、1972年にノーマン・ビッグスによって導入されました。^[9]ビッグスとトニー・ガーディナーは、1974年の未発表の原稿で奇数グラフの名前を説明しています。奇数グラフの各辺には、「異端者」である一意の要素を割り当てることができます。つまり、その辺に付随する頂点に関連付けられたいずれのサブセットにも属さない要素です。^{[10] [11]}${\displaystyle O_{n}}$

奇グラフは次数 の正則グラフです。頂点と辺を持ちます。したがって、 の頂点の数は ${\displaystyle O_{n}}$${\displaystyle n}$${\displaystyle {\tbinom {2n-1}{n-1}}}$${\displaystyle n{\tbinom {2n-1}{n-1}}/2}$${\displaystyle n=1,2,\dots }$

の 2 つの頂点が、一方の集合から要素を削除し、別の要素を追加することで互いに異なる集合に対応している場合、各頂点のペアが 1 回の追加と削除を実行する手順で、それらの頂点にアクセスできます。 の場合、これは最短経路です。それ以外の場合は、最初の集合から 2 番目の集合の補完集合へのこのタイプの経路を見つけ、さらに 1 ステップで 2 番目の集合に到達する方が短いです。したがって、 の直径はです。^{[1] [2]}${\displaystyle O_{n}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle 2k}$${\displaystyle 2k<n}$${\displaystyle O_{n}}$${\displaystyle n-1}$

すべての奇グラフは3弧推移的である。つまり、奇グラフ内のすべての有向3辺パスは、グラフの対称性によって他のすべてのそのようなパスに変換できる。 ^[12] 奇グラフは距離推移的であるため、距離正則である。^[2]距離正則グラフであるため、それらは交差配列によって一意に定義される。他の距離正則グラフは奇グラフと同じパラメータを持つことはできない。^[13]ただし、対称性が高いにもかかわらず、 の奇グラフは決してケイリーグラフにならない。^[14]${\displaystyle O_{n}}$${\displaystyle n>2}$

奇グラフは正則かつ辺推移的であるため、その頂点の接続性は次数に等しい。[ ^15]${\displaystyle n}$

の奇グラフは内周が 6 であるが、二部グラフではないにもかかわらず、奇閉路ははるかに長い。特に、奇グラフは内周が奇である。 -正則グラフが直径と内周が奇であり、異なる固有値のみを持つ場合、そのグラフは距離正則でなければならない。直径と内周が奇である距離正則グラフは一般化奇グラフと呼ばれ、奇グラフ自体だけでなく、折り畳み立方体グラフも含まれる。 ^[4]${\displaystyle n>3}$${\displaystyle O_{n}}$ ${\displaystyle 2n-1}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle 2n-1}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle 2n-1}$

を-元集合のサブセットから定義された奇グラフとし、をの任意のメンバーとします。このとき、 の頂点のうち、ちょうど 個の頂点が を含む集合に対応します。これらすべての集合は を含むため、互いに素ではなく、の独立集合を形成します。つまり、はサイズ の異なる独立集合を持ちます。エルデシュ・コー・ラドの定理から、これらはの最大独立集合であることがわかります。つまり、の独立数はです。さらに、すべての最大独立集合はこの形式である必要があるため、 はちょうど最大の独立集合を持ちます。^[2]${\displaystyle O_{n}}$${\displaystyle (2n-1)}$${\displaystyle X}$${\displaystyle x}$${\displaystyle X}$${\displaystyle O_{n}}$${\displaystyle {\tbinom {2n-2}{n-2}}}$${\displaystyle x}$${\displaystyle x}$${\displaystyle O_{n}}$${\displaystyle O_{n}}$${\displaystyle 2n-1}$${\displaystyle {\tbinom {2n-2}{n-2}}}$${\displaystyle O_{n}}$${\displaystyle O_{n}}$${\displaystyle {\tbinom {2n-2}{n-2}}.}$${\displaystyle O_{n}}$${\displaystyle 2n-1}$

が最大独立集合で、 を含む集合によって形成される場合、の補集合はを含まない頂点の集合です。この補集合はにおけるマッチングを誘導します。独立集合の各頂点はマッチングの頂点に隣接し、マッチングの各頂点は独立集合の頂点に隣接します。^{[2]この分解と、奇数グラフは二部グラフではないため、}彩色数は 3です。つまり、最大独立集合の頂点には 1 色を割り当てることができ、補集合に色を付けるにはさらに 2 色で十分です。 ${\displaystyle I}$${\displaystyle x}$${\displaystyle I}$${\displaystyle x}$${\displaystyle G}$${\displaystyle n}$${\displaystyle n-1}$

ヴィイジングの定理によれば、奇グラフの辺を彩色するのに必要な色の数はまたは であり、ピーターセングラフの場合はである。 が2 の累乗である場合、グラフの頂点の数は奇数であり、このことから辺の色の数は であることが再び導かれる。^[16]ただし、、、およびはそれぞれ色で辺を彩色することができる。^{[2] [16]}${\displaystyle O_{n}}$${\displaystyle n}$${\displaystyle n+1}$${\displaystyle O_{3}}$${\displaystyle n+1}$${\displaystyle n}$${\displaystyle n+1}$${\displaystyle O_{5}}$${\displaystyle O_{6}}$${\displaystyle O_{7}}$${\displaystyle n}$

ビッグス^[9]は、この問題を次のような物語で説明しています。架空の町クロームの11人のサッカー選手が、5人1組のチーム（外れた1人は審判を務める）を1386通りすべてでペアに組みたいと考えています。そして、各ペア間の試合を、各チームの6試合が6つの異なる曜日に行われ、日曜日はすべてのチームが休みになるようにスケジュールしたいと考えています。これは可能でしょうか？この物語では、各試合は のエッジを表し、各曜日は色で表され、 の6色のエッジカラーリングが、選手のスケジュール問題の解決策を提供します。 ${\displaystyle O_{6}}$${\displaystyle O_{6}}$

ピーターセングラフはよく知られた非ハミルトングラフだが、 の奇数グラフはすべてハミルトン閉路を持つことが知られている。^[17] 奇数グラフは頂点推移的であるため、頂点推移グラフのハミルトン閉路に関するロヴァースの予想に対する肯定的な答えが知られている特殊なケースの 1 つである。ビッグス^{[2] は、}より一般的に、 の辺は辺素なハミルトン閉路に分割できると予想した。が奇数のとき、残りの辺は完全なマッチングを形成する必要がある。このより強い予想は について検証された。^{[2] [16]}について、 の頂点の数が奇数であるため、 8 色の辺カラーリングは存在できないが、4 つのハミルトン閉路に分割される可能性は排除されない。 ${\displaystyle O_{3}}$${\displaystyle O_{n}}$${\displaystyle n\geq 4}$ ${\displaystyle O_{n}}$${\displaystyle \lfloor n/2\rfloor }$${\displaystyle n}$${\displaystyle n=4,5,6,7}$${\displaystyle n=8}$${\displaystyle O_{n}}$

• ワイスシュタイン、エリック W.、「奇数グラフ」、MathWorld