名称のあるグラフのギャラリーとは？わかりやすく解説

グラフ理論において、名前が付いたグラフの一覧を以下に示す。

特徴的なグラフ

バラバン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

完全グラフ

$n$

$K_{1}$

$K_{2}$

$K_{3}$

$K_{4}$

$K_{5}$

$K_{6}$

$K_{7}$

$K_{8}$

$K_{2,3}$

$K_{3,3}$

$K_{2,4}$

$K_{3,4}$

$C_{3}$

$C_{4}$

$C_{5}$

$C_{6}$

The friendship graphs F₂, F₃ and F₄.

フラーレングラフ

グラフ理論においてフラーレンとは、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つの頂点の完全グラフは正四面体の骨格を形作る。このように超立方体グラフは正多面体の骨格を表している。

立方体
$n=8$

正八面体
$n=6$

正十二面体
$n=20$

正二十面体
$n=12$

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

星

星 S_kは任意のkについて完全2部グラフ K_1,kの総称である。S₃は爪とも呼ばれる。

車輪グラフ

車輪グラフ W_nは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. MR 1441972.

[1] David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.

[2] Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic Journal of Combinatorics, DS6, 1-58, January 3, 2007. [1].

[3] Journal of Algorithms 23 (2): 345–358. (1997). doi:10.1006/jagm.1996.0806. MR 1441972.

[3]

名称のあるグラフのギャラリーとは？ わかりやすく解説