名称のあるグラフのギャラリー

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

特徴的なグラフ[編集]

バラバン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_{n}$ と書かれる。^[1]

$K_{1}$
$K_{2}$
$K_{3}$
$K_{4}$
$K_{5}$
$K_{6}$
$K_{7}$
$K_{8}$

完全2部グラフ[編集]

$K_{2,3}$
$K_{3,3}$ , the utility graph
$K_{2,4}$
$K_{3,4}$

閉路グラフ[編集]

$n$ 個の頂点を持つ閉路グラフはn-cycleと呼ばれ $C_{n}$ で表される。

$C_{3}$
$C_{4}$
$C_{5}$
$C_{6}$

フレンドシップグラフ[編集]

The フレンドシップグラフはn個の閉路グラフC₃ を一つの頂点で繋いで構成する。^[2]

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

フラーレングラフ[編集]

In graph theory, the term フラーレン refers to any 3-regular, planar graph with all faces of size 5 or 6 (including the external face). It follows from Euler's polyhedron formula, V – E + F = 2 (where V, E, F indicate the number of vertices, edges, and faces), that there are exactly 12 pentagons in a fullerene and V/2–10 hexagons. Fullerene graphs are the Schlegel representations of the corresponding fullerene compounds.

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$ , $m=12$
正八面体
$n=6$ , $m=12$
正十二面体
$n=20$ , $m=30$
正二十面体
$n=12$ , $m=30$

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

星[編集]

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

The star graphs S₃, S₄, S₅ and S₆.

車輪グラフ[編集]

車輪グラフ W_nはn個の頂点を持ち、一つの頂点が(n − 1)-閉路グラフのすべての頂点と結ばれたものを言う。

車輪グラフの例

W_{4}

–

W_{9}

.

出典[編集]

^ 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.

[1]

[2]

[3]