関連するグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/03/02 07:44 UTC 版)
タットグラフは1946年に発見された3-正則グラフであり、最初にハミルトン路が存在しないことが知られたグラフであるが、そのような声質を持つグラフの中で最小のグラフではない。 1965年にレーダーバーグは38頂点の Barnette–Bosák–Lederberg グラフを発見した。1968年には、グリンベルクがテイト予想の反例として42、44、46頂点のグリンベルクグラフを追加した。1974年には、フォークナーとヤンガーは42頂点と44頂点の反例を発見した。 そして1988年に、ホルトンとマッケイは6種類の38頂点からなるハミルトン路を持たない多面体を見つけた。それらは五角柱の2つの頂点をタットの小片に置き換えたものからなる。
※この「関連するグラフ」の解説は、「タットグラフ」の解説の一部です。
「関連するグラフ」を含む「タットグラフ」の記事については、「タットグラフ」の概要を参照ください。
関連するグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/03/06 10:20 UTC 版)
AT-freeな弦グラフとしての特徴づけにより、区間グラフは強弦グラフであり、パーフェクトグラフである。補グラフが比較可能グラフであり、その大小関係はその区間順序(interval order)である。 弦グラフでありその補グラフが比較可能であるという性質より、あるグラフとその補グラフの両方が区間グラフである場合、そしてその時に限りそれはスプリットグラフであり、置換グラフである。 任意の2区間が、重複区間を持たないかどちらかが完全に被覆する区間グラフは、自明なパーフェクトグラフ（英語版）である。 グラフのboxicityが1以上の場合、そしてその時に限り、そのグラフは区間グラフである。つまり、グラフ G の boxicity は区間グラフの辺集合の交差が G となるような頂点と同じ集合の区間集合の最小数である。 区間グラフの始点と終点を接続したものを円-弧グラフと呼び、全区間を円、区間を弧と呼ぶ。台形グラフも区間グラフの一般化である。連結グラフの内、三角形を含まない区間グラフはキャタピラ木である。
※この「関連するグラフ」の解説は、「区間グラフ」の解説の一部です。
「関連するグラフ」を含む「区間グラフ」の記事については、「区間グラフ」の概要を参照ください。
関連するグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/06/25 11:05 UTC 版)
「コンウェイの99グラフ問題」の記事における「関連するグラフ」の解説
より一般に、任意の辺がただ一つの三角形の1辺となり、任意の隣接しない2頂点がただ一つの四角形の向かい合う頂点となるような強正則グラフには、5通りのパラメータの組しか許されない。そのうち存在がわかっているのは2通りの組だけであり、頂点数が9のペイリーグラフ（英語版）（3-3 duoprism（英語版） のグラフ）はパラメータが (9,4,1,2) 、バーレカンプ–ヴァン・リント–ザイデルグラフはパラメータが (243,22,1,2) である。99グラフ問題は、5通りのパラメータの組の中で存在がわかっていないもののうち最小のものである。
※この「関連するグラフ」の解説は、「コンウェイの99グラフ問題」の解説の一部です。
「関連するグラフ」を含む「コンウェイの99グラフ問題」の記事については、「コンウェイの99グラフ問題」の概要を参照ください。
関連するグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 10:00 UTC 版)
ジョンソングラフ（英語版）は、n 元集合の k 元部分集合が頂点となり、その (k − 1)-元部分集合が一致するとき、各頂点が隣接するようなグラフである。k = 2 に対して、ジョンソングラフはクネーザーグラフ KGn,2 の補となる。ジョンソングラフは、ジョンソンスキーム（英語版）と密接に関係している。それらはいずれもセルマー・ジョンソン（英語版）の名にちなむ。 一般化クネーザーグラフ KGn,k,s とは、クネーザーグラフと頂点集合は同じものであるが、二つの頂点が連結するための必要十分条件が、それらに対応する集合が s 以下の共通部分を持つこと、であるようなグラフのことである (Denley 1997)。したがって、KGn,k,0 = KGn,k である。 2部クネーザーグラフ （bipartite Kneser graph）Hn,k は、n 個の元の集まりから抽出される k 個の元および n − k 個の元の集まりを頂点とするグラフである。二つの頂点が辺によって連結されているための必要十分条件は、一方の集合が他方の部分集合となっていることである。クネーザーグラフと同様に、2部クネーザーグラフは次数 ( n − k k ) {\displaystyle \textstyle {\binom {n-k}{k}}} でもって頂点推移的である。 2部クネーザーグラフは、KGn,k の2部二重被覆（英語版）として構成される。それにおいては、各頂点のコピーが作られ、各辺は、対応する頂点のペアを結び付けている辺と入れ替えられている (Simpson 1991)。2部クネーザーグラフ H5,2 はデザルググラフ（英語版）であり、2部クネーザーグラフ Hn,1 は王冠グラフ（英語版）である。
※この「関連するグラフ」の解説は、「クネーザーグラフ」の解説の一部です。
「関連するグラフ」を含む「クネーザーグラフ」の記事については、「クネーザーグラフ」の概要を参照ください。
- 関連するグラフのページへのリンク
