List of graphs#Gear

This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see Category:Graphs. Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts.

Individual graphs

File:Balaban 10-cage alternative drawing.svg|Balaban 10-cage

File:Balaban 11-cage.svg|Balaban 11-cage

File:Bidiakis cube.svg|Bidiakis cube

File:Brinkmann graph LS.svg|Brinkmann graph

File:Bull graph.circo.svg|Bull graph

File:Butterfly graph.svg|Butterfly graph

File:Chvatal graph.draw.svg|Chvátal graph

File:Diamond graph.svg|Diamond graph

File:Dürer graph.svg|Dürer graph

File:Ellingham-Horton 54-graph.svg|Ellingham–Horton 54-graph

File:Ellingham-Horton 78-graph.svg|Ellingham–Horton 78-graph

File:Errera graph.svg|Errera graph

File:Franklin graph.svg|Franklin graph

File:Frucht planar Lombardi.svg|Frucht graph

File:Goldner-Harary graph.svg|Goldner–Harary graph

File:GolombGraph.svg|Golomb graph

File:Groetzsch-graph.svg|Grötzsch graph

File:Harries graph alternative_drawing.svg|Harries graph

File:Harries-wong graph.svg|Harries–Wong graph

File:Herschel graph no col.svg|Herschel graph

File:Hoffman graph.svg|Hoffman graph

File:Holt graph.svg|Holt graph

File:Horton graph.svg|Horton graph

File:Kittell graph.svg|Kittell graph

File:Markström-Graph.svg|Markström graph

File:McGee graph.svg|McGee graph

File:Meredith graph.svg|Meredith graph

File:Moser spindle.svg |Moser spindle

File:Sousselier graph.svg|Sousselier graph

File:Poussin graph planar.svg|Poussin graph

File:Robertson graph.svg|Robertson graph

File:Sylvester graph.svg|Sylvester graph

File:Tutte fragment.svg|Tutte's fragment

File:Tutte graph.svg|Tutte graph

File:Young-Fibonacci.svg|Young–Fibonacci graph

File:Wagner graph ham.svg|Wagner graph

File:Wells graph.svg|Wells graph

File:Wiener-Araya.svg|Wiener–Araya graph

File:Windmill graph Wd(5,4).svg|Windmill graph

Highly symmetric graphs

=Strongly regular graphs=

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

File:Clebsch graph.svg|Clebsch graph

File:Cameron graph.svg|Cameron graph

File:Petersen1 tiny.svg|Petersen graph

File:Hall janko graph.svg|Hall–Janko graph

File:Hoffman singleton graph circle2.gif|Hoffman–Singleton graph

File:Higman Sims Graph.svg|Higman–Sims graph

File:Paley13 no label.svg|Paley graph of order 13

File:Shrikhande graph symmetrical.svg|Shrikhande graph

File:Schläfli graph.svg|Schläfli graph

File:Brouwer Haemers graph.svg|Brouwer–Haemers graph

File:Local mclaughlin graph.svg|Local McLaughlin graph

File:Perkel graph embeddings.svg|Perkel graph

File:Gewirtz graph embeddings.svg|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.

File:Heawood Graph.svg|Heawood graph

File:Möbius–Kantor unit distance.svg|Möbius–Kantor graph

File:Pappus graph.svg|Pappus graph

File:DesarguesGraph.svg|Desargues graph

File:Nauru graph.svg|Nauru graph

File:Coxeter graph.svg|Coxeter graph

File:Tutte eight cage.svg|Tutte–Coxeter graph

File:Dyck graph.svg|Dyck graph

File:Klein graph.svg|Klein graph

File:Foster graph.svg|Foster graph

File:Biggs-Smith graph.svg|Biggs–Smith graph

File:Rado graph.svg|The Rado graph

=Semi-symmetric graphs=

File:Folkman_Lombardi.svg|Folkman graph

File:Gray graph hamiltonian.svg|Gray graph

File:Ljubljana graph hamiltonian.svg|Ljubljana graph

File:Tutte 12-cage.svg|Tutte 12-cage

Graph families

=Complete graphs=

The complete graph on $n$ vertices is often called the $n$ -clique and usually denoted $K_n$ , from German komplett.David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.

File:Complete graph K1.svg| $K_1$

File:Complete graph K2.svg| $K_2$

File:Complete graph K3.svg| $K_3$

File:Complete graph K4.svg| $K_4$

File:Complete graph K5.svg| $K_5$

File:Complete graph K6.svg| $K_6$

File:Complete graph K7.svg| $K_7$

File:Complete graph K8.svg| $K_8$

=Complete bipartite graphs=

The complete bipartite graph is usually denoted $K_{n,m}$ . For $n=1$ see the section on star graphs. The graph $K_{2,2}$ equals the 4-cycle $C_4$ (the square) introduced below.

File:Biclique K 2 3.svg| $K_{2,3}$

File:Biclique K 3 3.svg| $K_{3,3}$ , the utility graph

File:Biclique K 2 4.svg| $K_{2,4}$

File:Biclique K 3 4.svg| $K_{3,4}$

=Cycles=

The cycle graph on $n$ vertices is called the n-cycle and usually denoted $C_n$ . It is also called a cyclic graph, a polygon or the n-gon. Special cases are the triangle $C_3$ , the square $C_4$ , and then several with Greek naming pentagon $C_5$ , hexagon $C_6$ , etc.

File:Complete graph K3.svg| $C_3$

File:Circle graph C4.svg| $C_4$

File:Circle graph C5.svg| $C_5$

File:Undirected 6 cycle.svg| $C_6$

=Friendship graphs=

The friendship graph F_n can be constructed by joining n copies of the cycle graph C₃ with a common vertex.Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic Journal of Combinatorics, DS6, 1-58, January 3, 2007. [http://www.combinatorics.org/Surveys/ds6.pdf] {{Webarchive|url=https://web.archive.org/web/20120131202557/http://www.combinatorics.org/Surveys/ds6.pdf |date=2012-01-31 }}.

File:Friendship graphs.svg

=Fullerene graphs=

In graph theory, a fullerene is any polyhedral 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.

File:Graph of 20-fullerene w-nodes.svg|20-fullerene (dodecahedral graph)

File:Graph of 24-fullerene w-nodes.svg|24-fullerene (Hexagonal truncated trapezohedron graph)

File:Graph of 26-fullerene 5-base w-nodes.svg|26-fullerene graph

File:Graph of 60-fullerene w-nodes.svg|60-fullerene (truncated icosahedral graph)

File:Graph of 70-fullerene w-nodes.svg|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.{{cite journal |journal=Journal of Algorithms |volume=23 |year=1997 |issue=2 |pages=345–358 |mr=1441972|doi=10.1006/jagm.1996.0806|title=A Constructive Enumeration of Fullerenes |last1=Brinkmann |first1=Gunnar |last2=Dress |first2=Andreas W.M }} G. Brinkmann also provided a freely available implementation, called [http://cs.anu.edu.au/~bdm/plantri/ 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.

File:3-cube column graph.svg|Cube
$n=8$ , $m=12$

File:Octahedral graph.circo.svg|Octahedron
$n=6$ , $m=12$

File:Dodecahedral graph.neato.svg|Dodecahedron
$n=20$ , $m=30$

File:Icosahedron graph.svg|Icosahedron
$n=12$ , $m=30$

=Truncated solids=

File:3-simplex_t01.svg|Truncated tetrahedron

File:Truncated cubical graph.neato.svg|Truncated cube

File:Truncated octahedral graph.neato.svg|Truncated octahedron

File:Truncated Dodecahedral Graph.svg|Truncated dodecahedron

File:Icosahedron t01 H3.png|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.

File:First Blanusa snark.svg|Blanuša snark (first)

File:Second Blanusa snark.svg|Blanuša snark (second)

File:Double-star snark.svg|Double-star snark

File:Flower snarkv.svg|Flower snark

File:Loupekine 1.svg|Loupekine snark (first)

File:Loupekine 2.svg|Loupekine snark (second)

File:Szekeres-snark.svg|Szekeres snark

File:Tietze's graph.svg|Tietze graph

File:Watkins snark.svg|Watkins snark

=Star=

A star S_k is the complete bipartite graph K_1,k. The star S₃ is called the claw graph.

File:Star graphs.svg

=Wheel graphs=

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

File:Wheel graphs.svg

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=

File:Gear graph.svg

A gear graph, denoted G_n, is a graph obtained by inserting an extra vertex between each pair of adjacent vertices on the perimeter of a wheel graph W_n. Thus, G_n has 2n+1 vertices and 3n edges.{{mathworld|urlname=GearGraph|title=Gear graph}} Gear graphs are examples of squaregraphs, and play a key role in the forbidden graph characterization of squaregraphs.{{citation|title=Combinatorics and geometry of finite and infinite squaregraphs|first1=H.-J.|last1=Bandelt|first2=V.|last2=Chepoi|first3=D.|last3=Eppstein|author3-link=David Eppstein|arxiv=0905.4537|journal=SIAM Journal on Discrete Mathematics|volume=24|issue=4|pages=1399–1440|year=2010|doi=10.1137/090760301|s2cid=10788524 }} Gear graphs are also known as cogwheels and bipartite wheels.

=Helm=

A helm graph, denoted H_n, is a graph obtained by attaching a single edge and node to each node of the outer circuit of a wheel graph W_n.{{mathworld|urlname=HelmGraph|title=Helm graph}}{{Cite web |url=http://www.combinatorics.org/Surveys/ds6.pdf |title=Archived copy |access-date=2008-08-16 |archive-url=https://web.archive.org/web/20120131202557/http://www.combinatorics.org/Surveys/ds6.pdf |archive-date=2012-01-31 |url-status=dead }}

=Lobster=

A lobster graph is a tree in which all the vertices are within distance 2 of a central path.{{cite web|url=http://groups.google.com/groups?selm=Pine.LNX.4.44.0303310019440.1408-100000@eva117.cs.ualberta.ca |title=Google Discussiegroepen |date= |accessdate=2014-02-05}}{{mathworld|urlname=Lobster Graph|title=Lobster Graph}} Compare caterpillar.

=Web=

Image:Cube graph.svg.]]

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

A web graph has also been defined as a prism graph Y_{n+1, 3}, with the edges of the outer cycle removed.{{mathworld|urlname=WebGraph|title=Web graph}}

References

Category:Mathematics-related lists