奇数グラフ
ピーターセングラフを一般化する対称グラフの族
奇数グラフ
お 3 ＝ K G （ 5 、 2 ） {\displaystyle O_{3}=KG(5,2)} ピーターセングラフ
頂点 （ 2 n − 1 n − 1 ） {\displaystyle {\tbinom {2n-1}{n-1}}}
エッジ n （ 2 n − 1 n − 1 ） / 2 {\displaystyle n{\tbinom {2n-1}{n-1}}/2}
直径 n − 1 {\displaystyle n-1} [1] [2]
胴回り3対5、6対6、それ以外[3] O 2 {\displaystyle O_{2}}
O 3 {\displaystyle O_{3}}
プロパティ距離推移
表記の上
グラフとパラメータの表
奇妙なグラフ O 4 = K G ( 7 , 3 ) {\displaystyle O_{4}=KG(7,3)}

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

奇グラフは高い奇内周を持ちます。つまり、奇数長の長い閉路は含まれますが、短い閉路は含まれません。しかし、このグラフの名前はこの性質に由来するものではなく、グラフの各辺に「外れた人」、つまり辺で結ばれた2つの集合に含まれない要素が存在するという事実に由来しています。

定義と例

奇グラフは、 -元集合の-元部分集合それぞれに対して1つの頂点を持つ。2つの頂点が辺で繋がれているのは、対応する部分集合が互いに素である場合に限る。[2]つまり、はクネザーグラフである。 O n {\displaystyle O_{n}} ( n − 1 ) {\displaystyle (n-1)} ( 2 n − 1 ) {\displaystyle (2n-1)} O n {\displaystyle O_{n}} K G ( 2 n − 1 , n − 1 ) {\displaystyle KG(2n-1,n-1)}

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

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

歴史と応用

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

これらのグラフの表記法は、 1972年にノーマン・ビッグスによって導入されました。[9]ビッグスとトニー・ガーディナーは、1974年の未発表原稿で奇グラフの名称を説明しています。奇グラフの各辺には、「外れ」となる唯一の要素、つまりその辺に接する頂点のいずれの部分集合にも属さない要素が割り当てられます。[10] [11] O n {\displaystyle O_{n}}

プロパティ

奇グラフは次数 の正則グラフである。奇グラフには頂点と辺がある。したがって、 の頂点の数は O n {\displaystyle O_{n}} n {\displaystyle n} ( 2 n − 1 n − 1 ) {\displaystyle {\tbinom {2n-1}{n-1}}} n ( 2 n − 1 n − 1 ) / 2 {\displaystyle n{\tbinom {2n-1}{n-1}}/2} n = 1 , 2 , … {\displaystyle n=1,2,\dots }

1、3、10、35、126、462、1716、6435（OEISのシーケンスA001700）。

距離と対称性

の2つの頂点が、一方の集合から要素を削除し、もう一方の集合から要素を追加することで互いに異なる集合に対応している場合、これらの頂点は、各頂点ペアが1回の追加と削除を行うステップで互いに到達できる。 の場合、これは最短経路である。そうでない場合、最初の集合から2番目の集合の補集合へのこの種の経路を見つけ、さらにもう1ステップで2番目の集合に到達する方が短い。したがって、 の直径はである。[1] [2] O n {\displaystyle O_{n}} k {\displaystyle k} k {\displaystyle k} 2 k {\displaystyle 2k} 2 k < n {\displaystyle 2k<n} O n {\displaystyle O_{n}} n − 1 {\displaystyle n-1}

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

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

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

独立集合と頂点彩色

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

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

エッジカラーリング

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

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

ハミルトン性

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

参考文献

  1. ^ ab Biggs, Norman L. (1976)、「保型グラフとクライン条件」、Geometriae Dedicata、5 (1): 117– 127、doi :10.1007/BF00148146。
  2. ^ abcdefghij ビッグス、ノーマン (1979)、「いくつかの奇数グラフ理論」、第2回国際組合せ数学会議、ニューヨーク科学アカデミー紀要、319 (1): 71– 81、Bibcode :1979NYASA.319...71B、doi :10.1111/j.1749-6632.1979.tb32775.x。
  3. ^ ウェスト、ダグラス・B.（2000年）「演習1.1.28」グラフ理論入門（第2版）、ニュージャージー州エングルウッドクリフス：プレンティス・ホール、17ページ。
  4. ^ ab Van Dam, Edwin; Haemers, Willem H. (2010),一般化奇グラフの奇特性評価、CentERディスカッションペーパーシリーズNo. 2010-47、SSRN  1596575。
  5. ^ Kowalewski, A. (1917)、「WR Hamilton's Dodekaederaufgabe als Buntordnungproblem」、Sitzungsber。アカド。ウィス。ウィーン (約 IIA)、126 : 67– 90, 963– 1007Biggs（1979）より引用。
  6. ^ Balaban, Alexandru T.; Fǎrcaşiu, D.; Bǎnicǎ, R. (1966), 「炭素イオンおよび関連系における多重1, 2シフトのグラフ」Rev. Roum. Chim. , 11 : 1205。
  7. ^バラバン、アレクサンドル・T. ( 1972)、「化学グラフ、第13部：組み合わせパターン」、ルーマニア数学出版、17 : 3–16。
  8. ^ Ghafoor, Arif; Bashkow, Theodore R. (1991)、「フォールトトレラント相互接続ネットワークとしての奇数グラフの研究」、IEEE Transactions on Computers、40 (2): 225– 232、Bibcode :1991ITCmp..40..225G、doi :10.1109/12.73594。
  9. ^ ab Biggs, Norman (1972), Guy, Richard K. (ed.), "An edge-colouring problem", Research Problems, American Mathematical Monthly , 79 (9): 1018– 1020, doi :10.2307/2318076, JSTOR  2318076。
  10. ^ アンドリース、ブラウワー;コーエン、アージェ M. Neumaier, A. (1989)、距離正規グラフ、Springer、ISBN 0-387-50619-5。
  11. ^ Ed Pegg, Jr. (2003年12月29日) Cubic Symmetric Graphs, Math Games, Mathematical Association of America、2010年8月21日時点のオリジナルよりアーカイブ、2010年8月24日閲覧。。
  12. ^ Babai、László (1995)、「自己同型群、同型、再構成」、Graham、Ronald L. ;マーティン・グレッシェル; Lovász、László (編)、Handbook of Combinatorics、vol. I、North-Holland、pp.  1447–1540、Proposition 1.9、2010 年 6 月 11 日のオリジナルからアーカイブ。
  13. ^ムーン、アリュン（1982）、「 パラメータによる奇グラフO kの特徴づけ」、離散数学、42（1）：91-97、doi：10.1016/0012-365X（82）90057-7。
  14. ^ Godsil, CD (1980)、「より奇数グラフ理論」、離散数学、32 (2): 205– 207、doi : 10.1016/0012-365X(80)90055-2。
  15. ^ ワトキンス、マーク・E.（1970）、「推移グラフの連結性」、組合せ理論ジャーナル、8：23-29、doi：10.1016/S0021-9800(70)80005-9、MR  0266804
  16. ^ abc メレディス、ガイ・HJ; ロイド、E. キース (1973)、「クロームのフットボール選手たち」、コンビナトリアル理論ジャーナル、シリーズB、15 (2): 161– 166、doi :10.1016/0095-8956(73)90016-6。
  17. ^ ミュッツェ、トルステン;ヌンメンパロ、ジェリー。 Walczak、Bartosz (2018)、「Sparse Kneser charts are Hamiltonian」、Journal of the London Mathematical Society、103 (4): 1253–1275、arXiv : 1711.01636、doi :10.1112/jlms.12406、MR  4273468
Retrieved from "https://en.wikipedia.org/w/index.php?title=Odd_graph&oldid=1330165563"