名称のあるグラフのギャラリー
グラフ理論において、名前が付いたグラフの一覧を以下に示す。
特徴的なグラフ
- バラバン10-ケージ(英語版)
- バラバン11-ケージ(英語版)
- ビディアキキューブ(英語版)
- ブリンクマングラフ(英語版)
- ブルグラフ(英語版)
- バタフライグラフ(英語版)
- フバータルグラフ(英語版)
- ダイアモンドグラフ(英語版)
- デューラーグラフ(英語版)
- Ellingham–Horton 54-graph
- Ellingham–Horton 78-graph
- Errera graph
- フランクリングラフ(英語版)
- フルフトグラフ(英語版)
- Goldner–Harary graph
- Grötzsch graph
- Harries graph
- Harries–Wong graph
- Herschel graph
- ホフマングラフ(英語版)
- Holt graph
- Horton graph
- Kittell graph
- Markström graph
- McGee graph
- Meredith graph
- Moser spindle
- Sousselier graph
- Poussin graph
- Robertson graph
-
-
- Young–Fibonacci graph
- Wagner graph
- Wiener–Araya graph
Highly symmetric graphs
- Clebsch graph
-
- Hall–Janko graph
- Hoffman–Singleton graph
- Higman–Sims graph
- Paley graph of order 13
- Shrikhande graph
- Schläfli graph
- Brouwer–Haemers graph
- Local McLaughlin graph
- Perkel graph
- Gewirtz graph
-
- メビウス-カントールグラフ(英語版)
- パップスグラフ(英語版)
- デザルググラフ(英語版)
- ナウルグラフ(英語版)
- コクセターグラフ(英語版)
- トゥッテ-コクセターグラフ(英語版)
- ディックグラフ(英語版)
- Klein graph
- フォスターグラフ(英語版)
- ビッグス-スミスグラフ(英語版)
- The ラドグラフ(英語版)
半対称グラフ
-
- グレイグラフ(英語版)
- リュブリャナグラフ(英語版)
- トゥッテ12-ケージ(英語版)
Graph families
完全グラフ
個の頂点を持つ完全グラフはと書かれる。[1]
-
- , the utility graph
-
-
閉路グラフ
個の頂点を持つ閉路グラフはn-cycleと呼ばれで表される。
フレンドシップグラフ
フレンドシップグラフはn個の 閉路グラフC3 を一つの頂点で繋いで構成する。[2]
フラーレングラフ
グラフ理論においてフラーレンとは、3-正則平面グラフであって無限面を含めて全ての面が五角形または六角形であるもの。オイラーの多面体公式 V – E + F = 2(V, E, F はそれぞれ頂点数、辺数、面数)から、フラーレンにはちょうど12個の五角形と V/2–10 個の六角形がある。フラーレングラフは対応するフラーレン化合物のシュレーゲル図(英語版)である。
- 20-fullerene (dodecahedral graph)
- 24-fullerene (Hexagonal truncated trapezohedron graph)
- 26-fullerene
- 60-fullerene (truncated icosahedral graph)
- 70-fullerene
同じ六角形の面の数で同型でないフラーレンを作るアルゴリズムがG. BrinkmannとA. Dressによって発表された。[3]
正多面体
4つの頂点の完全グラフは正四面体の骨格を形作る。このように超立方体グラフは正多面体の骨格を表している。
Truncated solids
- Truncated tetrahedron
- Truncated cube
- Truncated octahedron
- Truncated dodecahedron
- Truncated icosahedron
スナーク
スナーク はブリッジを持たない立方体グラフのうち辺彩色に4色必要なものの総称である。最も小さいスナークグラフはピーターセングラフである。
- Blanuša snark (first)
- Blanuša snark (second)
- Double-star snark
- Flower snark
- Loupekine snark (first)
- Loupekine snark (second)
- Szekeres snark
- Tietze graph
- Watkins snark
星
星 Skは任意のkについて完全2部グラフ K1,kの総称である。S3は爪とも呼ばれる。
車輪グラフ
車輪グラフ Wnはn個の頂点を持ち、一つの頂点が(n − 1)-閉路グラフのすべての頂点と結ばれたものを言う。
出典
[脚注の使い方]
- ^ David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.
- ^ Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic Journal of Combinatorics, DS6, 1-58, January 3, 2007. [1].
- ^ Journal of Algorithms 23 (2): 345–358. (1997). doi:10.1006/jagm.1996.0806. MR1441972.