List of graphs

Short description: none

## Contents

* 1 Individual graphs
* 2 Highly symmetric graphs
* 2.1 Strongly regular graphs
* 2.2 Symmetric graphs
* 2.3 Semi-symmetric graphs
* 3 Graph families
* 3.1 Complete graphs
* 3.2 Complete bipartite graphs
* 3.3 Cycles
* 3.4 Friendship graphs
* 3.5 Fullerene graphs
* 3.6 Platonic solids
* 3.7 Truncated solids
* 3.8 Snarks
* 3.9 Star
* 3.10 Wheel graphs
* 4 Other graphs
* 4.1 Gear
* 4.2 Helm
* 4.3 Lobster
* 4.4 Web
* 5 References

## Individual graphs

* Balaban 10-cage

* Balaban 11-cage

* Bidiakis cube

* Brinkmann graph

* Bull graph

* Butterfly graph

* Chvátal graph

* Diamond graph

* Dürer graph

* Ellingham–Horton 54-graph

* Ellingham–Horton 78-graph

* Errera graph

* Franklin graph

* Frucht graph

* Goldner–Harary graph

* Golomb graph

* Grötzsch graph

* Harries graph

* Harries–Wong graph

* Herschel graph

* Hoffman graph

* Holt graph

* Horton graph

* Kittell graph

* Markström graph

* McGee graph

* Meredith graph

* Moser spindle

* Sousselier graph

* Poussin graph

* Robertson graph

* Sylvester graph

* Tutte's fragment

* Tutte graph

* Young–Fibonacci graph

* Wagner graph

* Wells graph

* Wiener–Araya graph

* Windmill graph

## Highly symmetric graphs

### Strongly regular graphs

The strongly regular graph on v vertices and rank k is usually denoted srg(v,k,λ,μ).

* Clebsch graph

* Cameron graph

* Petersen 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

### Symmetric graphs

A symmetric graph is one in which there is a symmetry (graph automorphism) taking any ordered pair of adjacent vertices to any other ordered pair; the Foster census lists all small symmetric 3-regular graphs. Every strongly regular graph is symmetric, but not vice versa.

* Heawood graph

* Möbius–Kantor graph

* Pappus graph

* Desargues graph

* Nauru graph

* Coxeter graph

* Tutte–Coxeter graph

* Dyck graph

* Klein graph

* Foster graph

* Biggs–Smith graph

* The Rado graph

### Semi-symmetric graphs

* Folkman graph

* Gray graph

* Ljubljana graph

* Tutte 12-cage

## Graph families

### Complete graphs

The complete graph on n vertices is often called the n-clique and usually denoted Kn, from German komplett.[1]

* K1

* K2

* K3

* K4

* K5

* K6

* K7

* K8

### Complete bipartite graphs

The complete bipartite graph is usually denoted Kn,m. For n=1 see the section on star graphs. The graph K2,2 equals the 4-cycle C4 (the square) introduced below.

* K2,3

* K3,3, the utility graph

* K2,4

* K3,4

### Cycles

The cycle graph on n vertices is called the n-cycle and usually denoted Cn. It is also called a cyclic graph, a polygon or the n-gon. Special cases are the triangle C3, the square C4, and then several with Greek naming pentagon C5, hexagon C6, etc.

* C3

* C4

* C5

* C6

### Friendship graphs

The friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex.[2]

The friendship graphs F2, F3 and F4.

### Fullerene graphs

In graph theory, the term fullerene 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 h = V/2 – 10 hexagons. Therefore V = 20 + 2h; E = 30 + 3h. Fullerene graphs are the Schlegel representations of the corresponding fullerene compounds.

* 20-fullerene (dodecahedral graph)

* 24-fullerene (Hexagonal truncated trapezohedron graph)

* 26-fullerene graph

* 60-fullerene (truncated icosahedral graph)

* 70-fullerene

An algorithm to generate all the non-isomorphic fullerenes with a given number of hexagonal faces has been developed by G. Brinkmann and A. Dress.[3] G. Brinkmann also provided a freely available implementation, called fullgen.

### Platonic solids

The complete graph on four vertices forms the skeleton of the tetrahedron, and more generally the complete graphs form skeletons of simplices. The hypercube graphs are also skeletons of higher-dimensional regular polytopes.

* Cube
n=8, m=12

* Octahedron
n=6, m=12

* Dodecahedron
n=20, m=30

* Icosahedron
n=12, m=30

### Truncated solids

* Truncated tetrahedron

* Truncated cube

* Truncated octahedron

* Truncated dodecahedron

* Truncated icosahedron

### Snarks

A snark is a bridgeless cubic graph that requires four colors in any proper edge coloring. The smallest snark is the Petersen graph, already listed above.

* 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

### Star

A star Sk is the complete bipartite graph K1,k. The star S3 is called the claw graph.

The star graphs S3, S4, S5 and S6.

### Wheel graphs

The wheel graph Wn is a graph on n vertices constructed by connecting a single vertex to every vertex in an (n − 1)-cycle.

Wheels W4 – W9.

## Other graphs

This partial list contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own.

### Gear

A gear graph, denoted Gn, is a graph obtained by inserting an extra vertex between each pair of adjacent vertices on the perimeter of a wheel graph Wn. Thus, Gn has 2n+1 vertices and 3n edges.[4] Gear graphs are examples of squaregraphs, and play a key role in the forbidden graph characterization of squaregraphs.[5] Gear graphs are also known as cogwheels and bipartite wheels.

### Helm

A helm graph, denoted Hn, is a graph obtained by attaching a single edge and node to each node of the outer circuit of a wheel graph Wn.[6][7]

### Lobster

A lobster graph is a tree in which all the vertices are within distance 2 of a central path.[8][9] Compare caterpillar.

### Web

The web graph W4,2 is a cube.

The web graph Wn,r is a graph consisting of r concentric copies of the cycle graph Cn, with corresponding vertices connected by "spokes". Thus Wn,1 is the same graph as Cn, and Wn,2 is a prism.

A web graph has also been defined as a prism graph Yn+1, 3, with the edges of the outer cycle removed.[7][10]

## References

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. ↑ Brinkmann, Gunnar; Dress, Andreas W.M (1997). "A Constructive Enumeration of Fullerenes". Journal of Algorithms 23 (2): 345–358. doi:10.1006/jagm.1996.0806.
4. ↑ Weisstein, Eric W.. "Gear graph". http://mathworld.wolfram.com/GearGraph.html.
5. ↑ Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010), "Combinatorics and geometry of finite and infinite squaregraphs", SIAM Journal on Discrete Mathematics 24 (4): 1399–1440, doi:10.1137/090760301
6. ↑ Weisstein, Eric W.. "Helm graph". http://mathworld.wolfram.com/HelmGraph.html.
7. ↑ 7.0 7.1 "Archived copy". http://www.combinatorics.org/Surveys/ds6.pdf.
8. ↑ "Google Discussiegroepen". http://groups.google.com/groups?selm=Pine.LNX.4.44.0303310019440.1408-100000@eva117.cs.ualberta.ca. Retrieved 2014-02-05.
9. ↑ Weisstein, Eric W.. "Lobster". http://mathworld.wolfram.com/Lobster.html.
10. ↑ Weisstein, Eric W.. "Web graph". http://mathworld.wolfram.com/WebGraph.html.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/List of graphs. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=List_of_graphs&oldid=202686"